BOJ 1812 - 사탕

문제

BOJ 1812 - 사탕

N명이 원형으로 앉아 있고, 인접한 두 사람의 사탕 합이 주어질 때 각 사람의 사탕 수를 구하라.

입력

사람 수 N과 N개의 인접 쌍의 합이 주어진다 (i번째 값은 i번과 i+1번의 합).

출력

각 사람의 사탕 수를 한 줄에 하나씩 출력한다.

예제

풀이

전체 합과 짝수 간격 합의 차이로 각 개인값을 역산한다.

1. 모든 쌍의 합의 총합은 각 사람의 값이 2번씩 더해진 것이므로 전체 합 / 2가 개인 합이다
2. 각 사람 i에서 시작하여 짝수 간격으로 쌍의 합을 더하면 특정 패턴이 나온다
3. 짝수 간격 합 - 전체 합 / 2로 각 사람의 값을 구한다

핵심 아이디어: 원형 배열에서 교대 합을 이용하면, 전체 합과의 차이로 각 원소를 O(N)에 복원할 수 있다.

코드

#include <iostream>
using namespace std;
int main(void)
{
  int n;
  int arr[1000], sum = 0;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> arr[i];
    sum += arr[i];
  }
  sum /= 2;
  for (int i = 0; i < n; i++)
  {
    int tmp = 0;
    for (int j = 0; j < n; j += 2)
      tmp += arr[(i + j) % n];
    cout << tmp - sum << '\n';
  }
}

복잡도

• 시간: O(N²)
• 공간: O(N)