[Baekjoon] 19532번: 수학은 비대면강의입니다

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

19532번: 수학은 비대면강의입니다

 

---

 

문제 해결 과정

착안

연립일차방정식(system of linear equations)은 행렬의 곱셈의 정의에 의하여 행렬 형태로 나타낼 수 있다.

 

$$a_{11} x_{1} + a_{12} x_{2} + \cdots + a_{1n} x_{n} = b_{1}$$

$$a_{21} x_{1} + a_{22} x_{2} + \cdots + a_{2n} x_{n} = b_{2}$$

$$\vdots$$

$$a_{m1} x_{1} + a_{m2} x_{2} + \cdots + a_{mn} x_{n} = b_{m}$$

 

즉 위와 같은 \(m\)개의 방정식으로 이루어진 \(n\)원 연립일차방정식(미지수가 \(n\)개)과 아래의 행렬 표현은 동치이다.

 

$$\begin{equation*} \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m1} & \cdots & a_{mn} \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{bmatrix} = \begin{bmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{m} \end{bmatrix} \end{equation*}   \Longleftrightarrow   \mathbf{A} \mathbf{x} = \mathbf{b}$$

 

이때, 주어진 행렬 \(\mathbf{A}\)의 역행렬이 존재(\(\det \mathbf{A} \neq 0\))하는 경우, \(\mathbf{A}\mathbf{x} = \mathbf{b}\)의 해 \(\mathbf{x}\)가 유일하게 존재하고,

$$\mathbf{x} = \mathbf{A^{-1}}\mathbf{b}$$

이다(행렬 \(\mathbf{A}\)가 가역행렬인지의 여부와 \(\mathbf{A}\)의 행렬식(determinant), \(\det \mathbf{A}\) 사이의 관계는 선형대수학을 공부하여 알 수 있다).

 

구현

문제에서 주어지는 2개의 이원일차연립방정식을 만족하는 (\(x, y\))가 항상 유일하게 존재하도록 방정식의 계수가 주어진다고 하였으므로, 방정식의 계수를 성분으로 가지는 행렬 \(\mathbf{A}\)는 항상 역행렬이 존재(invertible)한다. 따라서,

$$\begin{equation*} \begin{bmatrix} a & b \\ d & e \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} c \\ f \end{bmatrix} \end{equation*}   \Longleftrightarrow   \mathbf{A} \mathbf{x} = \mathbf{b}$$

을 만족하는 해 (\(x, y\))는

$$\begin{bmatrix} x \\ y \end{bmatrix} = \mathbf{x} = \mathbf{A^{-1}}\mathbf{b} = {1 \over {ae-bd}} \begin{bmatrix} e & -b \\ -d & a \end{bmatrix} \begin{bmatrix} c \\ f \end{bmatrix} = {1 \over {ae-bd}} \begin{bmatrix} ce-bf \\ af-cd \end{bmatrix}$$

 

로 구할 수 있다(이차정사각행렬의 역행렬을 구하는 방법). 이때, 문제에서 \(x\), \(y\)가 \(-999 \leq x, y \leq 999\)를 만족하는 정수라고 전제하였기 때문에, 단순 int형의 나눗셈을 통해 답을 구하고자 했다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int main()
{
	int a, b, c, d, e, f;
	scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f);
	
	int det = a * e - b * d;
	printf("%d %d\n", (c * e - b * f) / det, (a * f - c * d) / det);

	return 0;
}

 

실행 결과

 

관련 알고리즘으로 브루트 포스 알고리즘이 나오던데, 이 문제의 어떤 부분이 브루트 포스 알고리즘인지 전혀 모르겠다...