PKU 1844. Sum. AC get!~

#include <stdio.h> int main() { int i, j, sum = 0; scanf("%d", &i); for (j = 1; j < 1024 * 1024 * 1204; j++) { sum += j; if (sum >= i) { if (!((sum - i) % 2)) { printf("%d\n", j); break; } } } return 0; }

흐음.

이번에도 쉬운 문제이지요?

1부터 N까지 숫자를 나열해 두고, 각 숫자마다 부호를 아무렇게나 둔 다음,

부호까지 붙인 수들을 합해서 S가 되게 만들되, 그 N중 최소를 출력하는 겁니다.

제 솔루션은 간단합니다.

1부터 N까지의 합을 그냥 구합니다. -_-;

이 때 1부터 N까지의 합이 S보다 크다면, S는 1부터 N까지의 숫자중 몇개를 뽑아서 만들 수 있다는 거지요.

그 말인 즉슨, S보다 큰 1부터 N까지의 합이 나와야 N이 답이 될 가능성이 있다는 겁니다.

12 = -1 + 2 + 3 + 4 + 5 + 6 - 7 이지요?

12 = 1 + 2 + 3 + 4 + 5 + 6 + 7  - 1 - 7

이리 둬봤는데...

어색하더군요. 만들 방법이 읍드만 -_-;

근데 이걸 반복하다 문득 느낀 것.

"최소일땐 1부터 N까지의 합에서 S를 뺀 게 2의 배수다 -_-!"

.... 무려 1부터 20까지 노가다를 뛰었습니다.

20까지는 맞습니다.

냈어요.

AC 됐구요.

-_-;