BOJ 5623 - 수열의 합

문제

S[i][j] = a[i] + a[j]인 N x N 행렬이 주어질 때, 원래 수열 a를 복원하라.

입력

수열 길이 N과 N x N 합 행렬이 주어진다.

출력

복원된 수열을 공백으로 구분하여 출력한다.

예제

입력	출력
`3` `0 3 5` `3 0 4` `5 4 0`	`2 1 3`

풀이

세 원소의 쌍합을 이용하여 첫 원소를 구하고 나머지를 역산한다.

a[1] = (S[1][2] + S[1][3] - S[2][3]) / 2로 첫 번째 원소를 구한다
나머지 원소는 a[i] = S[1][i] - a[1]로 구한다

핵심 아이디어: S[1][2] + S[1][3] - S[2][3] = 2*a[1]이므로, 세 쌍합의 관계식으로 한 원소를 결정하면 나머지는 자동으로 결정된다.

코드

#include <cstdio>
int S[1001][1001] = {};
int main(void)
{
  int N, one;
  scanf("%d", &N);
  int ans[1001] = {};
  for (int i = 1; i <= N; i++)
  {
    for (int j = 1; j <= N; j++)
    {
      scanf("%d", &S[i][j]);
    }
  }
  if (N != 2)
  {
    one = (S[1][2] + S[1][3] - S[2][3]) / 2;
    for (int i = 1; i <= N; i++)
    {
      if (i == 1)
        ans[i] = one;
      else
      {
        ans[i] = S[1][i] - one;
      }
      printf("%d ", ans[i]);
    }
  }
  else
  {
    printf("1 1");
  }
}

복잡도

시간: O(N²) (입력 읽기)
공간: O(N²)

문제