출처: https://train.usaco.org/usacogate
문제 설명
For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.
For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets
are identical:
- {3} and {1,2}
This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and
thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same
sum:
- {1,6,7} and {2,3,4,5}
- {2,5,7} and {1,3,4,6}
- {3,4,7} and {1,2,5,6}
- {1,2,4,7} and {3,5,6}
Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.
Your program must calculate the answer, not look it up from a table.
입력
The input file contains a single line with a single integer representing N, as above.
출력
The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition.
입력 예
7
출력 예
4
문제 풀이 내용
{1, 2, ..., N} 인 집합을 합이 같은 2개의 집합으로 나누는 경우의 수를 구하는 문제이다. 전체의 합은 N*(N+1)/2 이고 이것을 2개의 같은 값으로 나누는 것이기 때문에 N*(N+1)/4 = k. 즉, N % 4 = 0 or -1(3) 인 경우만 가능하다.
이 경우의 수는 조건에 맞는 모든 부분집합을 찾아서 그 수를 구할 수 있다. N = 4K 인 경우는 A = { (1, 4), (5,8), ..., (4K+1, 4K+4)}, B = { (2, 3), (6,7), ... , (4K+2, 4K+3)} 의 두 집합으로 나눈뒤 한쪽의 특정한 값을 가진 수의 조합을 다른 쪽에서 같은 값을 가진 조합으로 변경해서, 다른 집합들을 찾을 수 있다. N = 4K+3 인 경우는 A = { (1,2), (5,5), ... (4K+1, 4K+2)}, B = { (0,3), (4, 7), ... , (4K, 4K+3)}으로 초기 집합을 나눌 수 있다.
부분 집합들을 직접 찾지 않고, 아래 같은 규칙을 이용해서 경우의 수를 세는 것도 가능하다. 다만 어떤 부분 집합이 가능한지는 알 수 없다.
... | ... | ... | N*(N+1)/4 = K | ... | |
{1, 2, ..., i} | ... | ... | ... | A(i, K) | ... |
{1, 2, ..., i+1} | ... | A(i+1, K-(i+1)) | ... | A(i+1, K) | ... |
A(i+1, K) 의 값은 새로운 수 (i+1)이 원하는 합을 만드는데 사용한 경우< A(i+1, K-(i+1))>와 사용하지 않는 경우<A(i, K)>의 합이 된다. A(i+1, K) = A(i, K) + A(i+1, K-(i+1))
이 값들을 구하는데, A(0,0) = 1. (empty set), A(k, 0) = 1(empty set) 을 가지고 시작해서 완성한다.
프로그램 내용
int main()
{
unsigned long N;
fin >> N;
if( N % 4 == 1 || N % 4 == 2)
fout << "0" << endl;
int sum = N*(N+1) / 4;
long long DP[800][40] = {0};
DP[0][0] = 1;
for (int idx1=1; idx1 <= N ; ++idx1)
for (int idx2 = 0; idx2 <= sum ; ++idx2)
DP[idx2][idx1] = DP[idx2][idx1-1];
for (int idx2 = 0; idx2 <= sum -idx1; ++idx2)
DP[idx2+idx][idx1] += DP[idx2][idx1-1];
fout << DP[sum][N-1] << "\n";
Chapter 2. Bigger Challenges
'USACO Training' 카테고리의 다른 글
Problem 1.5.3 Mother's Milk (0) | 2019.10.12 |
---|---|
Problem 2.3.4 Money Systems (0) | 2019.10.11 |
Problem 2.1.5 Sorting A Three-Valued Sequence (0) | 2019.09.18 |
Problem 2.1.4 Ordered Fractions (0) | 2019.09.18 |
Problem 2.2.5 Runaround Numbers (0) | 2019.09.18 |