출처: 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

+ Recent posts