점화식
같은 수가 연속해서 나오면 안 된다.
dp는 2차원 배열로 설정
dp [n][1] n을 만드는 수 중 마지막 자리가 1
dp [n][2] 마지막 자리가 2
dp [n][3] 마지막 자리가 3
그렇다면 어떻게 계산해야 할 까?
dp [n][1] 은 마지막 자리가 1 인 숫자이므로
그 전 단계에서 마지막 자리가 2,3 인 숫자가 올 수 있다
점화식
dp[n][1] = dp [n-1][2]+dp [n-1][3];
dp [n][2] = dp [n-2][1]+dp [n-2][3];
dp [n][3] = dp [n-3][1]+dp [n-3][2];
이 점화식이 이해가 되지 않는다면
https://suhyeokeee.tistory.com/24?category=837216
이 글에 나와있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
public class Main {
static int n,t;
static StringBuilder sb = new StringBuilder();
static int dp[][] = new int[100001][4];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
dp[1][1]=1;
dp[1][2]=0;
dp[1][3]=0;
dp[2][1]=0;
dp[2][2]=1;
dp[2][3]=0;
dp[3][1]=1;
dp[3][2]=1;
dp[3][3]=1;
for(int i=4; i<=100000; i++) {
dp[i][1] = (dp[i-1][2]+dp[i-1][3])%1000000009;
dp[i][2] = (dp[i-2][1]+dp[i-2][3])%1000000009;
dp[i][3] = (dp[i-3][1]+dp[i-3][2])%1000000009;
}
t = Integer.parseInt(br.readLine());
while(t-- >0) {
int sum = 0;
n= Integer.parseInt(br.readLine());
sum +=dp[n][1];
sum%=1000000009;
sum+=dp[n][2];
sum%=1000000009;
sum+=dp[n][3];
sum%=1000000009;
}
System.out.println(sb);
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
">cs |
'알고리즘' 카테고리의 다른 글
[백준 11058] 크리보드 -JAVA // le_effort// (0) | 2020.03.10 |
---|---|
[백준 2293] 동전 1 -JAVA //le_effort// (0) | 2020.03.10 |
[백준 15989] 1,2,3 더하기 4 -JAVA // le_effort// (1) | 2020.03.09 |
[백준 15988] 1,2,3 더하기 3 -JAVA// le_effort// (0) | 2020.03.09 |
[백준 12101] 1,2,3 더하기2 -JAVA// le_effort// (0) | 2020.03.09 |