시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 731 | 156 | 119 | 22.119% |
세 변수 \(x_1\), \(x_2\), \(x_3\)로 이루어진 일차 방정식 세 개가 있다. \(a_{ij}\)와 \(b_i\)가 주어졌을 때, 다음과 같이 표현할 수 있다.
\(\begin{vmatrix} a_{ 11 }x_{ 1 }+a_{ 12 }x_{ 2 }+a_{ 13 }x_{ 3 }=b_{ 1 } \\ a_{ 21 }x_{ 1 }+a_{ 22 }x_{ 2 }+a_{ 23 }x_{ 3 }=b_{ 2 } \\ a_{ 31 }x_{ 1 }+a_{ 32 }x_{ 2 }+a_{ 33 }x_{ 3 }=b_{ 3 } \end{vmatrix}\)
행렬과 벡터를 이용하면 다음과 같이 나타낼 수 있다.
\(A\cdot x=b\), where \(A=\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}\), \(b=\begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix}\), x=\(\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}\)
크래머의 공식을 이용하면 방정식의 해는 행렬식(determinant)를 이용해 다음과 같이 구할 수 있다.
\(x_i = \frac {det~A_i}{det~A}\)
\(A_i\) 는 행렬 \(A\)의 \(i\)번째 열을 벡터 \(b\)로 대체한 것이다. 예를 들어, \(3 \times 3\) 행렬의 행렬식은 아래와 같이 구할 수 있다.
\(det\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} = a_{11}(a_{22}a_{33} - a_{23}a_{32}) - a_{12}(a_{21}a_{33} - a_{23}a_{31}) + a_{13}(a_{21}a_{32}-a_{22}a_{31})\)
크래머의 공식은 \(det~A \ne 0\)인 경우에만 해를 구할 수 있다. \(det~A \ne 0\)인 경우에 방정식의 해는 유일하고, 그렇지 않은 경우에는 해가 없거나 무수히 많은 해를 가진다.
방정식이 많은 경우에는 행렬식을 구하는데 시간이 너무 많이 걸린다. 따라서, 이런 경우에는 다른 방법을 사용하는 것이 더 효율적이다.
세 변수로 이루어진 일차 방정식 세 개가 주어진다. 크래머의 공식을 이용해서 해를 구하는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스는 세 줄로 이루어져 있고, 아래와 같은 순서로 주어진다.
\(\begin{matrix} a_{11} & a_{12} & a_{13} & b_1 \\ a_{21} & a_{22} & a_{23} & b_{2} \\ a_{31} & a_{32} & a_{33} & b_{3} \end{matrix}\)
모든 숫자는 -1000보다 크거나 같고, 1000보다 작거나 같은 정수이며, 공백 한 칸으로 구분되어져 있다.
각 테스트 케이스마다 두 줄을 출력한다.
첫째 줄에는 행렬 \(A_1\), \(A_2\), \(A_3\), \(A\)의 행렬식을 출력한다.
방정식의 해가 존재하지 않는 경우에는 둘째 줄에 "No unique solution"을 출력하고, 해가 존재하는 경우에는 "Unique solution: "와 \(x_1\), \(x_2\), \(x_3\) 값을 소수점 셋째자리까지 출력한다.
방정식의 해 \(x_i\)가 -0.0005 < \(x_i\) < 0.0005 인 경우에는 "-0.000" 대신에 "0.000"을 출력한다.
각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.
3 4 0 0 1 0 2 0 2 0 0 1 4 1 2 3 1 1 1 1 2 2 2 2 3 1 0 0 1 0 1 0 0 0 0 -1 0
2 8 32 8 Unique solution: 0.250 1.000 4.000 1 -2 1 0 No unique solution -1 0 0 -1 Unique solution: 1.000 0.000 0.000
University > Tu-Darmstadt Programming Contest > TUD Contest 2001 2번