「プロジェクトオイラー問７６」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問７６ - (2014/03/02 (日) 09:31:28) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2076
*Problem 76 「和の数え上げ」 †
5は数の和として6通りに書くことができる:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

2つ以上の正整数の和としての100の表し方は何通りか.



解法
足す数を辞書順で考える。
例えば
5＝3+1+1だと３が一番大きな数で合計が5で左が３という情報以外組み合わせの計算にいらなくなる。
9を作るとき5＝3+1+1の左に4を足して9＝4+3+1+1、すると合計が9で左が4という情報だけ残しておけばよいｔ。
7＝6+1の左に2を足して9を作ろうとしても辞書順は壊れる。
これを考慮して動的計画法を立てると簡単に求まる。
Ｗｉｋｉの分割数のほうが解き方としては本格的だが、実装はできても原理がよくわからないので掲載していない。



 #include<stdio.h>
 #include<string.h>
 
 int memo[101][101];
 
 int main(){
 	memset(memo,0,sizeof(memo));
  	for(int i=1;i<100;i++){
  		memo[i][i]=1;
 	}
 	for(int i=2;i<=100;i++){
 		for(int j=1;j<i;j++){
 			for(int k=1;k<=j;k++){
 				memo[i][j]+=memo[i-j][k];
 			}
  		}
	}
  	int ans=0;
 	for(int i=1;i<=99;i++){
 		ans+=memo[100][i];
 	}
 	printf("%d\n",ans);
 }