PKU 1844. Sum. [판정:AC]

#include <stdio.h> int sigma( int k ) { return k*( k+1 )/2; } void main() { int s; int sum; int i; scanf("%d", &s); for( i = 1; ; i++ ) { sum = sigma(i); if( ( sum >= s ) && ( sum%2 == s%2 ) ) { printf("%d\n", i); break; } } }

이번 문제는 '저번에 비해' 너무 쉬워서 미칠 지경이군요 -_-;



풀이는 이렇습니다


우선 수열 {Sn}을 정의하는데, 'Sn = 1부터 n까지의 합'이라고 합시다

그러면 이 수열은 아래와 같은 값을 갖는데, 한가지 규칙이 있습니다
S1 = 1,
S2 = 1 + 2 = 3,
S3 = 1 + 2 + 3 = 6,
S4 = 1 + 2 + 3 + 4 = 10, …

S1, S2는 홀수, S3, S4는 짝수, 다시 S5, S6은 홀수, S7, S8은 짝수, …


이제 우리는 주어진(scanf로 입력받은) 합 s에 대해 s ≤ Sk를 만족하는 어떤 k를 찾으면 됩니다

원문 안에 있는 샘플을 예로 들어봅시다

주어진 합 s는 12입니다

12에 대해 Sk가 12보다 크거나 같아지는 k는 5 이상이면 됩니다 (∵ S5 = 1 + 2 + 3 + 4 + 5 = 15 이므로)

그런데 한가지 문제가 생기는 것이 있으니,
15를 12로 만들기 위해 1, 2, 3, 4, 5 중 하나의 부호를 바꾸어야 하는데
어느 한 수를 잡아서 부호를 마이너스로 바꿔주는 순간 실제 값은 그 수의 2배가 줄어들게 되죠

그렇기 때문에, 주어진 합 12와 합동이 되는 Sk를 찾아야 원하는 결과를 얻을 수 있습니다
(여기서 합동이란, '2로 나눈 나머지가 같은 수'를 의미하는 것으로 하겠습니다)
(즉, 짝수의 합동은 짝수이고, 홀수의 합동은 홀수입니다)


위의 규칙을 보면 Sk가 12와 합동이 되면서 12보다 크거나 같으려면 k는 7 이상이면 됩니다

그래서 S7을 살펴보면, S7 = 1 + … + 7 = 28이고,
이것은 주어진 합과 16의 차이를 보이므로 절반인 8에 해당하는 숫자들을 골라 부호를 바꿔주면 됩니다

원문 안의 샘플은 -1 + 2 + 3 + 4 + 5 + 6 - 7 이라 하였지만,
이 뿐만 아니라 1 - 2 + 3 + 4 + 5 - 6 + 7도 가능하고, 1 + 2 - 3 + 4 - 5 + 6 + 7 역시 가능합니다



이제 이것을 '10만 이하의 임의의 s'에 대해서 계산하려면

위에서 했던 두가지 조건만을 체크하면 됩니다
'Sk ≥ s인 어떤 자연수 k를 찾을 수 있느냐'와 '그 Sk와 s가 합동이냐'

이 두 조건을 만족하는 최소의 k를 찾는 순간, 다른 어떤 연산도 할 필요 없이 k를 출력하면 문제는 끝입니다 :)