boj)15590 - 1, 2, 3 더하기 5
2020. 9. 17. 14:13ㆍPS/boj
import java.util.*;
public class boj_15990 {
static final long mod = 1000000009L;
static final int limit = 100000;
static long[][] d = new long[limit+1][4];
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
for (int i=1; i<=limit; i++) {
if (i-1 >= 0) {
d[i][1] = d[i-1][2] + d[i-1][3];
if (i == 1) {
d[i][1] = 1;
}
}
if (i-2 >= 0) {
d[i][2] = d[i-2][1] + d[i-2][3];
if (i == 2) {
d[i][2] = 1;
}
}
if (i-3 >= 0) {
d[i][3] = d[i-3][1] + d[i-3][2];
if (i == 3) {
d[i][3] = 1;
}
}
d[i][1] %= mod;
d[i][2] %= mod;
d[i][3] %= mod;
}
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
System.out.println((d[n][1] + d[n][2] + d[n][3])%mod);
}
}
}
- 생각이 안난다 ....
- 머리가 굳은거같다 ....
- 합의 마지막에 올 수 있는 수는 1, 2, 3이 있다.
- 마지막에 1 올 경우 그 앞은 2, 3 -> dp[i][1] = dp[i-1][2] + dp[i-1][3];
- 마지막에 2 올 경우 그 앞은 1, 3 -> dp[i][2] = dp[i-2][1] + dp[i-2][3];
- 마지막에 3 올 경우 그 앞은 2, 3 -> dp[i][3] = dp[i-3][2] + dp[i-3][3];
- 이중배열로 dp를 담는다.
'PS > boj' 카테고리의 다른 글
boj)2193 - 이친수 (0) | 2020.09.17 |
---|---|
boj)10844 - 쉬운 계단 수 (0) | 2020.09.17 |
boj)16194 - 카드 구매하기 2 (0) | 2020.09.17 |
boj)11052 - 카드 구매하기 (0) | 2020.09.17 |
boj)9095 - 1, 2, 3 더하기 (0) | 2020.09.16 |