Algorithm, boj, 합분해(2225)
풀이 & 틀린이유
- 예제를 그리면서 규칙성을 찾기 어려울때는 n번째일때의 큰 그림을 생각해보자..!!
- dp[n][0] (n번째 칸에 사자가 없을때)
- dp[n-1][0] + dp[n-1][1] + dp[n-1][2];
- dp[n][1] (n번째 칸의 왼쪽에 사자가 있을때) => 그 이전 칸에는 사자가 없거나 오른쪽에만 사자가 있어야 하므로
- dp[n][2] = dp[n-1][0] + dp[n-1][1]
소스
package org.baekjoon;
import java.util.Scanner;
public class test1309_dp_zoo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] dp = new int[N+1][3];
for (int i = 1; i < N+1; i++) {
if (i==1) {
dp[i][0] = 1;dp[i][1] = 1;dp[i][2] = 1;
}
else
{
dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901;
dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901;
dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % 9901;
}
}
int result = 0;
for (int i=0; i<3; i++)
result += dp[N][i];
System.out.println(result % 9901);
}
}
Reference
