[22940] 선형 연립 방정식

문제 링크 : https://www.acmicpc.net/problem/22940

22940 - 선형 연립 방정식

본문

하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 즉, 다음과 같은 식을 의미한다.

\[A_1x_1 + A_2x_2 + \cdots + A_nx_n = B\]

선형 연립 방정식이란 유한개의 선형 방정식의 모임이다. 예를 들면 다음과 같다.

\[x_1 + 2x_2 = 4 \\ 3x_1 + 2x_2 = 6\]

선형 연립 방정식이 주어졌을 때, 해를 구하는 프로그램을 작성하라.

유일한 해가 존재하는 경우만 입력으로 주어지며, 해는 모두 100 이하의 자연수이다.

입력

첫째 줄에 미지수의 수 $N$ ($2 \leq N \leq 6$)이 주어진다.

둘째 줄부터 $N$ 개의 줄에 걸쳐 각 방정식을 나타내는 $N+1$개의 정수 $A_1, A_2, \cdots, A_N$, $B$ ($1 \leq A_i \leq 10$)가 주어진다.

출력

$x_1$부터 $x_N$까지 순서대로 한 칸의 공백을 사이에 두고 출력한다.

제한

시간 제한	메모리 제한
2sec	512MB

---

풀이

문제가 너무 직관적이다. 연립방정식을 주고 그 답을 찾으라고 한다. 심지어 답은 항상 유일한 해가 존재한다고 보장되어있다. IF를 생각할 필요가 없다는 뜻으로 이해할 수 있다.

연립방정식을 푸는 방법은 많겠지만, 그것을 컴퓨터에게 이해시키는 것은 어려울 것 같다. 필자는 이 문제에서는 가우스 소거법이라는 방법을 사용하여 해를 구하였다. 연립방정식을 matrix 형태로 변환하고 각 행을 소거 연산을 통해 정리하고, 각 변수의 결과를 보여줄 수 있는 풀이 방법이다.

이 문제에서는 아래와 같은 절차로 소거법을 진행하였다.

• 모든 열(column)에 대하여 반복한다
  • 행들 중, column의 값이 0이 아니면서 “이미 방문하지 않았고” column의 절댓값이 가장 작은 행을 고른다
    • 방문하지 않았다는 것은, 이전에 선택된 적이 없다는 뜻이다
  • 선택된 행의 column 값을 1로 조절한다 (행 자체를 column 값으로 나눠주면 된다)
  • 다른 모든 행에 대해, 선택된 행과 연립시켜 column의 값이 0이 되도록 한다
• 결과값은, row 중 값이 1인 column이 하나 있을텐데, 그것을 $i$라고 한다면, matrix[i][n]에 존재하게 된다

기본적으로 가우스 소거법 알고리즘을 적용하는 문제라서 아이디어 자체는 어렵지 않다. 알고리즘을 본의대로 구현할 수 있는가를 확인하는 문제라고 생각하면 될 것 같다.

여담으로, 문제에서 주어지는 수와 문제의 해답이 전부 정수로 되어있다. 그런데 연산 과정에서 정수 범위를 벗어나는 경우가 있는 것 같다. int로는 틀렸다만 matrix의 값을 double형으로 지정하니 맞았습니다를 받을 수 있었다.

• 참고 알고리즘 : 가우스 소거법

코드

사용 언어 : C

최종 수정일 : 2023 / 2 / 15

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX 6
#define NONE -1

double matrix[MAX_IDX][MAX_IDX + 1];
int rowIndex[MAX_IDX];
bool visit[MAX_IDX + 1];
int n;

#define abs(x) (((x) < 0) ? (-(x)) : (x))

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        rowIndex[i] = NONE;
        visit[i] = false;
        for (int j = 0; j <= n; ++j) {
            scanf("%lf", &matrix[i][j]);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (visit[j] == true) {
                continue;
            } else if (rowIndex[i] == NONE ||
                       (matrix[j][i] != 0 &&
                        abs(matrix[j][i]) < abs(matrix[rowIndex[i]][i]))) {
                rowIndex[i] = j;
            }
        }
        visit[rowIndex[i]] = true;
        double temp = matrix[rowIndex[i]][i];
        for (int a = 0; a <= n; ++a) {
            matrix[rowIndex[i]][a] /= temp;
        }

        for (int a = 0; a < n; ++a) {
            if (rowIndex[i] == a) {
                continue;
            }
            double temp = matrix[a][i];
            for (int b = 0; b <= n; ++b) {
                matrix[a][b] -= (temp * matrix[rowIndex[i]][b]);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        printf("%.0lf ", matrix[rowIndex[i]][n]);
    }
    return 0;
}

• matrix[][] : 연립방정식을 행렬 꼴로 기록
• rowIndex[] : index를 column으로 생각했을 때, 행들 중 column의 절댓값을 최소로 하는 행의 번호를 기록
  • 이 때, 0은 논외로 친다