dynamic programming 7 subset

문제는 더블릿 21 dynamic programming에 있는 subset입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/subset/subset.php?pname=subset

N까지의 합을 반으로 나누었을 때 이 나뉘어진 반의 합이 같은 수인 경우의 수를 구하는 문제입니다.

간단히 설명하면 1~N까지의 수의 합(N(N+1)/2)의 반이 되는 1~N까지의 합의 경우의 수를 구하고 반으로 나누면 됩니다.

예를 들어 입력으로 7이 들어왔을 경우 1~7까지의 합의 반은 14인데 1~7까지의 합 중에 14가 되는 경우의 수를 구하고 이의 반을 출력해주면 됩니다.

이를 위해 각 수까지의 합의 경우의 수를 가지고 있는 배열을 선언해줍니다.

ar[40];

0까지의 수를 가지고 만들 수 있는 수는 0이고 이 때의 경우의 수는 1입니다.

ar[0]=1;

1까지의 수를 가지고 만들 수 있는 수는 0, 1이 있습니다.

ar[0]=1;

ar[1]=1;

2까지의 수를 가지고 만들 수 있는 수는 3까지 있는데 0, 1, 2, (1, 2) 각각 1개씩 있습니다.

ar[0]=1;

ar[1]=1;

ar[2]=1;

ar[3]=1;

3까지의 수를 보겠습니다.

ar[0]=1;

ar[1]=1;

ar[2]=1;

ar[3]=2;  //(1, 2)와 3 : 2가지의 경우의 수가 있습니다.

ar[4]=1;

ar[5]=1;

ar[6]=1;

이렇게 쭉 구해주면 되는데 예를 들어 입력이 7일 때의 합을 구하려면 7까지의 수가 들어왔을 때 14를 만들 수 있는 경우의 수의 반이니까 ar[14]/2가 정답이 되게 됩니다.

그럼 몇의 수까지의 합을 구할 때 이 합이 어디까지 갈 수 있는지를 알아야 합니다.  4가 들어왔을 때 1~4까지의 모든 합은 4*5/2입니다.  1~4까지의 수를 이용해 ar[10]까지 구할 수 있다는 것입니다.

ar[10]은 어떻게 나오냐면 1~3까지의 합에 4를 더해준 값입니다.  1~3까지의 합은 ar[6]입니다.  ar[6]에서 숫자 하나를 더해준다고 경우의 수가 증가하진 않습니다.

ar[10]+=ar[6];  //초기 ar[10]은 0

ar[9]는 ar[5]에 4를 더해준 값이 됩니다.  

ar[9]+=ar[5];

이렇게 ar[4]까지 갱신해줄 수 있는데 ar[4]는 ar[0]에서 4만 더한 값입니다.

ar[4]+=ar[0];

이렇게 거꾸로 가는 이유는 밑에서부터 올라올 경우 ar[4]의 값에 4가 추가되어 갱신이 되고 4가 이미 추가된 값을 이용해 ar[8]을 계산하기 때문입니다.  ar[8]은 4가 추가되기 전 1~3까지의 수로 구할 수 있는 4가 나올 수 있는 경우의 수ar[4]에서 구해져야 합니다.  그렇기 때문에 위에서부터 거꾸로 내려갑니다.

위에서 파란색을 표시한 것이 해당 수가 더해질 때 갱신되는 값으로 이는 더해지는 수를 a라고 할 때 a(a+1)/2~a의 범위입니다.  그리고 a(a+1)/2는 a(a+1)/2-a, a(a+1)/2-1은 a(a+1)/2-1-a에 의해 갱신됩니다.  이를 이용해 값을 N이 들어올 때까지 갱신해주고 N까지의 합의 반이 되는 인덱스의 절반을 출력해주면 됩니다.