자연수 n이 주어졌다고 가정해 봅시다. 우리는 처음 n개의 자연수(1부터 n까지)를 두 집합 A와 B로 나누어야 합니다. 이때 각 원소는 정확히 하나의 집합에만 속해야 하며, 집합 A의 원소 합과 집합 B의 원소 합 사이의 절댓값 차이가 최소가 되도록 만들어야 합니다. 그리고 그 최소 차이 값을 구하는 것이 목표입니다.
예를 들어 입력이 n = 5라면 출력은 1이 됩니다. A = {1, 3, 4}, B = {2, 5}로 나누면 각각의 합은 8과 7이 되고, 따라서 차이는 1이기 때문입니다.
풀이 아이디어
처음 n개의 자연수 전체의 합은 다음과 같이 계산할 수 있습니다.
S = n * (n + 1) / 2
두 집합의 합을 각각 Sa, Sb라고 하면 Sa + Sb = S가 성립합니다. 이때 두 합의 차이는 |Sa − Sb| = |S − 2 × Sb|로 표현되는데, 2 × Sb는 항상 짝수이므로 이 차이의 홀짝성(parity)은 전체 합 S와 같습니다.
따라서:
- S가 짝수이면 두 집합의 합을 정확히 같게 만들 수 있으므로 최소 차이는 0
- S가 홀수이면 차이는 최소한 1이며, 실제로 1로 만드는 분할이 항상 존재하므로 최소 차이는 1
결국 답은 전체 합을 2로 나눈 나머지, 즉 다음 한 줄로 구할 수 있습니다.
단계
이 문제는 아래 수식 하나로 해결됩니다.
return (n * (n + 1) / 2) % 2
예시 코드
아래 C++ 구현을 통해 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n) {
return (n * (n + 1) / 2) % 2;
}
int main() {
int n = 5;
cout << solve(n) << endl;
}입력
5
출력
1
복잡도 분석
이 풀이는 반복문 없이 산술 연산만 사용하므로 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)입니다. n이 매우 커지는 경우에는 오버플로우를 방지하기 위해 64비트 정수형(long long)을 사용하는 것이 안전합니다.