Kannondou [AIZU ONLINE JUDGE 0168]

judge.u-aizu.ac.jp

動的計画法の問題です。

・dp[i] = i 段目まで上るときの上り方の総数

とします。

0段目、1段目まで上るときの上り方の総数は、明らかに 1 です。

・dp[0] = 1
・dp[1] = 1

2段目まで上るときの上り方の総数は、2 です。
0,1,2 と上る上り方と、0,2 と上る上り方です。

3段目まで上がるときの上り方の総数は、

・0段目まで上るときの上り方の総数
・1段目まで上るときの上り方の総数
・2段目まで上るときの上り方の総数

これらを足し合わせると求まります。
なぜこのようにすると求まるのかを考えてみます。

まず、問題にあるように、段数は一度に3段まで上ることができます。
よって、3段目にちょうど上るときのパターンは、以下の3パターンしかありません。

・0 → 3
・1 → 3
・2 → 3

一番下のパターンの場合、2段目まで上って、その後3段目に上るときの上り方の総数は、2段目まで上るときの上り方の総数に等しいです。3段目に上るときの上り方は1通りしかないので、2段目まで上るときの上り方の総数×1ということですね。

上の2つも同様に考えると、i 段目まで上るときの上り方の総数は、i-1, i-2, i-3 段目まで上るときの上り方の総数を足し合わせたものになっていることがわかります。

このことを動的計画法の遷移式に落とし込むと、

・dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

となります。トリボナッチ数列の求め方と似ていますね。

遷移式が求まったので、後はこれを dp[30] まで遷移させて、dp[n]/3650 を切り上げたものを出力すればよいです。

void solve () {

	while (true) {
		int n = nextInt();
		if (n == 0) return;

		int[] dp = new int[31];
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		for (int i=3; i<=30; i++) {
			dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
		}

		out.println((dp[n]+3649)/3650);

	}

}

double型を経由せずに切り上げるやり方があることを知りました。
a/b を切り上げる場合は、

・(a+b-1)/b

とすればいいみたいです。覚えておきたいですね。