본문으로 바로가기

[백준 15990] 1,2,3 더하기5 -JAVA //le_effort//

category 알고리즘 2020. 3. 9. 17:12

점화식

같은 수가 연속해서 나오면 안 된다.

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

 

 

[백준 15989] 1,2,3 더하기 4 -JAVA // le_effort//

이해하는데 정말 오래 걸렸다.... 한 시간 반은 걸린 거 같다.... 문제에서 주어진 것 처럼 중복을 없애야 한다. 일단 dp를 2차원 배열로 설정한다. - POINT A dp[n][1] 정수 n을 표현한 수 중 1로 끝나는 것 dp..

suhyeokeee.tistory.com

이 글에 나와있다.

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
import java.io.*;
import java.util.*;
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;
            sb.append(sum+"\n");
        }
        System.out.println(sb);
    }
}
 
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
">cs