[알고리즘 문제]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 테이블의 크기
        int[][] ary = new int[n + 1][n + 1]; // 테이블을 표현할 배열
        int[] A = new int[n + 1]; // A수열을 저장 할 배열
        int a3; // A[3]값

        for (int i = 1; i <= n; i++) { // 편의를 위해 범위를 0~n-1까지가 아니라, 0~n로 설정
            for (int j = 1; j <= n; j++) {
                ary[i][j] = sc.nextInt();
            }
        }

        a3 = (ary[2][3] + ary[1][3] - ary[1][2]) / 2; // 방정식으로 해결, 문제에서 A[1]+A[2]=3, A[2]+A[3]=5, A[1]+A[3]=6이기 때문에
                                                      // A[1],A[2],A[3]을 미지수로 놓고정리하여 A[3]을 제외하고 모두 우항으로 넘긴다.
        A[3] = a3; // a3은 곧 A[3]값 이므로 A[3]은 초기화

        for (int i = 1; i <= n; i++) {

            if (i == 3) {
                continue;
            }

            A[i] = ary[3][i] - a3; // ary 각 행과 열의 값을 인덱스로 하는 A배열의 합(A[행]+A[열])의 값은 ary[행][열]값과 같다.
        } // 문제에서 ary[2][3] = 5, A[2]+A[3]=5 이기 때문에, A[3]행 값은 이미 알고 있기 때문에 이 값을 사용하여 나머지
          // 값을 구함.

        for (int s = 1; s <= n; s++) {
            System.out.print(A[s] + " ");
        }
    }
}

이 문제는 처음 설명을 읽었을 떄, 이해가 잘 안됐다. 한 3~4번 읽어보고 밑에 힌트까지 읽어보고나서 문제를 이해할 수가 있었다.

행렬과 수열이 있을 때, 행렬의 2행 3열의 값에는 수열의 2번쨰 값+수열의 3번째 값이 들어가게 된다. 대신 행과 열이 같은 경우에는 0이 들어가게 된다. 이런 규칙에서 행렬이 주어졌을 때, 수열의 값을 구하는 문제이다.

 

아이디어는 수열에서 하나의 값만 알 수 있다면 나머지 값을 모두 알 수 있다. 왜냐하면 각 수열에서 n번째 값의 합이 행렬에 나와있기 때문이다. 그렇다면 수열에서 하나의 값은 어떻게알 수 있을까 ?

 

방법은 연립방정식 사용했다. 먼저 수열을 A라는 배열로 표시하겠다. A[1]+A[2]=ary[1][2], A[2]+A[3]=ary[2][3], A[1]+A[3]=ary[1][3] 일때,  A[1]+A[3]=ary[1][3]에서 A[1]+A[2]=ary[1][2]를 빼면 A[3]-A[2] = ary[13]-ary[12]가 나온다. 이를 사용하여 A[2]+A[3]=ary[2][3]와 계산하면 A[3]을 구할 수 있다.

 

마지막으로 A배열을 돌면서 A[n]+A[3]=ary[n][3]에서 A[n]을 좌항에 두고 모두 우항에 옮김으로써 A수열을 구할 수 있다.