[C/C++] 백준 #1812 사탕(수학)

이번 문제는 N명의 학생들이 있는데, 학생들이 원형으로 둘러 앉아있습니다.  각 학생들은 사탕을 가지고 있는데, 우리가 알고 있는 것은 이웃한 두 학생들의 사탕의 합만을 알고 있습니다.  이 때, N명은 홀수라는 것이 중요합니다.

 

 

이 문제는 N이 홀수가 아니라면 풀기 어려운 문제가 됩니다.

 

각 학생들이 가지고 있는 사탕의 개수를 \(c_i\)라고 하자,  그리고 \(c_i + c_{i+1}\)을 \(s_i\)라고 하자.  참고로 \(c_{N+1} = c_1\)로 규정하도록 한다.  그러면 다음과 같은 식을 만들 수 있다.

 

\[ \sum_{i=1}^{N} (-1)^{i+1} s_i = 2c_1 \]

 

만약 짝수의 학생들이 있었다면, 위식은 0이 된다.  예를 들어서 5명의 학생이 사탕을 2, 3, 1, 4, 3개씩 가지고 있다면, 이웃한 두 학생의 합은 5, 4, 5, 7, 5 로 표현할 수 있다.  위의 식에 따라서 우리가 계산을 하면, 첫번째 학생의 사탕의 개수는 \( (5-4+5-7+5)/2 = 2 \)가 된다.  그러면, 첫번째 학생의 사탕의 개수를 알았으니, 차례대로 이전 학생의 사탕개수를 빼주면 된다.  두번째 학생은 3개, 세번째 학생은 1개, 네번째 학생은 4개, 다섯번째 학생은 3개가 됩니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------
//    baekjoon #1812
//        - by Aubrey Choi
//        - created at 2019-07-31
//--------------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, f=0;
    int v[999];
    scanf("%d", &n);
    for(int i=0; i < n; i++)
    {
        scanf("%d", v+i);
        f += (i&1)?-v[i]:v[i];
    }
    f/=2;
    printf("%d\n", f);
    for(int i=0; i < n-1; i++)
    {
        f = v[i]-f;
        printf("%d\n", f);
    }
    return 0;
}