백준 5623번 수열의 합 :: 마이구미

이 글은 백준 알고리즘 문제 5623번 "수열의 합" 을 풀이한다.

방법으로는 수학을 이용한 풀이가 된다.

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

양의 정수 N개로 이루어진 수열 A가 있다. 상근이는 수열 A의 모든 두 수의 합을 알고 있다. 이 때, 수열 A를 구하는 프로그램을 작성하시오.

다음 N개 줄에는 100,000보다 작거나 같은 양의 정수가 N개씩 주어진다. 이 숫자들은 S를 이루는 숫자이며, S(i,j) = A[i] + A[j] (i≠j), S(i,j) = 0 (i=j) 이다. S(i,j)는 i번째 줄, j번째 숫자를 의미하며, A[i]는 A의 i번째 수이다.

S(i,j) = A[i] + B[j] 이 부분만 이해하면 쉽게 문제를 해결 할 수 있다.

4
0 3 6 7
3 0 5 6
6 5 0 9
7 6 9 0

위와 같은 입력을 표현한다면, 다음과 같다.

S(1, 2) = 3
S(2, 3) = 6
S(1, 3) = 7

(1, 2) 와 (2, 1) 는 같다는 것을 알고 있다. (2, 3) == (3, 2), (1, 3) == (3, 1)

보기 쉽게 1, 2, 3 을 a, b, c 로 표현해보자.

a + b = 3
b + c = 6
a + c = 7

모두 더하게 되면 다음의 결과를 얻을 수 있다.

2(a + b + c) = 16
=> a + b + c = 8

이미 우리는 두 개의 알파벳을 더한 결과를 알고 있다.

b + c = 6
a + 6 = 8
=> a = 2

a 를 알게 되면 b 또한 바로 알 수 있게 된다.

a + b = 3
=> 2 + b = 3
=> b = 1

수학 문제 - 관련 문제 카테고리 

Github - https://github.com/hotehrud/acmicpc/tree/master/math

private void solve() {
    int n = sc.nextInt();
    int[][] array = new int[n + 1][n + 1];
    int[] a = new int[n + 1];
    StringBuilder sb = new StringBuilder();
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            array[i][j] = sc.nextInt();
        }
    }
 
    if (n == 2) {
        System.out.println("1 1");
    } else {
        a[1] = ((array[1][2] + array[2][3] + array[1][3]) / 2) - array[2][3];
        sb.append(a[1] + " ");
        for (int i = 2; i <= n; i ++) {
            a[i] = array[i - 1][i] - a[i - 1];
            sb.append(a[i] + " ");
        }
        System.out.println(sb.toString());
    }
}