[BOJ] 16283번: Farm (C++)

0. 문제

https://www.acmicpc.net/problem/16283

 

양의 수를 x, 염소의 수를 y라고 할 때, 다음 연립방정식의 해를 구하는 문제이다.

$$ \left\{\begin{matrix}
x+y=n \\ ax+by=w
\end{matrix}\right. $$ 

주의할 점은, 양과 염소가 각각 한 마리 이상 있어야하고, 가능한 해가 두 개 이상 있는 경우 혹은 없을 경우 -1를 출력하는 것이다.

1. 아이디어

 2 ≤ n ≤ 1,000이므로 x+y=n인 쌍을 모두 확인하는 브루트포스 알고리즘으로 해결할 수 있으나, 선형연립방정식을 푸는 문제인만큼 수학적으로 풀어보도록 한다. 행렬을 이용하여 연립방정식의 해를 구하거나, 문제 규칙에 따른 유효성을 검증한다.

 

2. 풀이

위 연립방정식은 행렬을 이용하면 다음과 같이 나타낼 수 있다.

$$ \begin{bmatrix}
1 & 1 \\
a & b \\
\end{bmatrix}
\begin{bmatrix}
x \\ y
\end{bmatrix} 
=
\begin{bmatrix}
n \\ w
\end{bmatrix}  $$

이 표현을 $Ax=b$의 형태라고 할 때, $x=A^{-1}b$임을 이용하여 해를 구할 수 있다. 그러나 $A$가 비가역적일 경우, 해를 구할 수 없고, 이때 해는 존재하지 않거나 무한하다. 문제에서 '만약 가능한 해가 두 개 이상 있는 경우 혹은 가능한 해가 없을 경우, -1 을 출력한다'고 했으므로, $A$의 가역성 조건에 따라 예외처리를 한다.

$A^{-1}=\frac{adj(a)}{\left| A \right|}$이므로,  $b-a \neq  0$일 때 가역적이다. 즉 그 반대의 경우 비가역적이다. 이 케이스를 예외처리한다.

if (a == b)
{
    if (n * a == w && n == 2)
    {
        std::cout << "1 1" << std::endl;
    }
    else
    {
        std::cout << -1 << std::endl;
    }
    return 0;
}

$a=b$인 경우 중 $n=2$이고 $an=w$인 경우에 -1을 출력하는 것이 아닌 $x=1, y=1$ 해를 출력하는 이유는, 문제에서 구하라는 해가 실수해가 아닌 자연수해이기 때문이다. 해당 경우에 존재하는 자연수해는 $x=1, y=1$로, $A$의 비가역성과 무관하게 유일하다. 해당 케이스에 대한 설명을 붙이면, 양과 염소 수의 합이 2로 각각 1마리씩 존재하며, 먹는 사료 양이 동일하고 $w$가 나머지 조건에 대해 유효한 경우이다.

 

이제 $A$가 가역행렬인 경우에 대해 풀어보자. 이 선형연립방정식의 해는 다음과 같이 구해진다.

 

$ \begin{bmatrix}
x \\ y
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
a & b \\
\end{bmatrix}^{-1}
\begin{bmatrix}
n \\ w
\end{bmatrix} $

 

$ \begin{bmatrix}
x \\ y
\end{bmatrix}
=
\frac{1}{b-a}
\begin{bmatrix}
b & -1 \\
-a & 1 \\
\end{bmatrix}
\begin{bmatrix}
n \\ w
\end{bmatrix} $

 

$ \begin{bmatrix}
x \\ y
\end{bmatrix}
=
\frac{1}{b-a}
\begin{bmatrix}
bn-w \\ -an+w
\end{bmatrix} $

 

$ \left\{\begin{matrix}x=\frac{bn-w}{b-a} \\ y=\frac{-an+w}{b-a}\end{matrix}\right. $

이제 구한 해를 코드에 옮겨 적는다.

int numer = b * n - w;
int denom = b - a;
if (numer % denom != 0)
{
    std::cout << -1 << std::endl;
    return 0;
}
int x = numer / denom;
int y = n - x;
if (x <= 0 || y <= 0)
{
    std::cout << -1 << std::endl;
    return 0;
}

다시 한 번 말하자면, 구하는 해는 실수해가 아닌 자연수해다. 나머지 연산을 통해 정수가 나오는지 확인하고, 해당 계산 후 x와 y가 1 이상인지 확인한다. y는 위에서 구한 해가 아닌 전체 수 n에서 x를 빼서 간단하게 구했다.

3. 정리

수학적으로 식을 정리하여 풀어내는 방법을 선택했다면, 문제에서 요구하는 답의 범위를 생각하는 것이 중요하다. 이번 문제의 경우는 자연수해를 구하는 것이 핵심이었다. 아래는 문제에 대한 전체 솔루션 코드이다.

#include <iostream>

int main()
{
    int a, b, n, w;
    std::cin >> a >> b >> n >> w;
    if (n > w)
    {
        std::cout << -1 << std::endl;
        return 0;
    }
    if (a == b)
    {
        if (n * a == w && n == 2)
        {
            std::cout << "1 1" << std::endl;
        }
        else
        {
            std::cout << -1 << std::endl;
        }
        return 0;
    }
    int numer = b * n - w;
    int denom = b - a;
    if (numer % denom != 0)
    {
        std::cout << -1 << std::endl;
        return 0;
    }
    int x = numer / denom;
    int y = n - x;
    if (x <= 0 || y <= 0)
    {
        std::cout << -1 << std::endl;
        return 0;
    }
    std::cout << x << " " << y << std::endl;
}