Cooper's devlog

1, 2, 3 더하기 3 : 15988 - JAVA 본문

Algorithm/Baekjoon

1, 2, 3 더하기 3 : 15988 - JAVA

cooper_dev 2020. 7. 13. 22:14

1. 문제 링크

https://www.acmicpc.net/problem/15988

 

15988번: 1, 2, 3 더하기 3

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

www.acmicpc.net

 

2. 문제 설명

3. 문제 접근

-dp문제는 주로 규칙성을 찾고 점화식을 작성하는 것이 핵심이다!!

 

(1) 문제의 규칙성을 확인하기 위해 표를 작성해서 비교!

N 1 2 3 4(합계)
1 1 0 0 1
2 1 1 0 2
3 2 1 1 4
4 4 2 1 7
5 7 4 2 13
6 13 7 4 24
7 24 13 7 44
8 44 24 13 81
9 81 44 24 149

 

(2) 표에 표시한 값들의 규칙을 확인해보기[하단 표 색깔끼리 비교해보기]

N 1 2 3 4(합계)
1 1 0 0 1
2 1 1 0 2
3 2 1 1 4
4 4 2 1 7
5 7 4 2 13
6 13 7 4 24
7 24 13 7 44
8 44 24 13 81
9 81 44 24 149

※규칙성(N >= 4)

-(N,1) = N-1의 합

-(N,2) = N-2의 합

-(N,3) = N-3의 합

 

 

(3)규칙성 확인 후, 점화식 작성

dp[row][1] = dp[row-1][4];

dp[row][2] = dp[row-2][4];

dp[row][3] = dp[row-3][4];

 

4. 문제 풀이

 

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
import java.util.Scanner;
 
public class sumOf123_3_2 {
    static long div = 1000000009;
    static long [] dp = new long[1000001];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(sc.nextLine());
        
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for (int tc = 1; tc <= T; tc++) {
            int    data = Integer.parseInt(sc.nextLine());
            
            for (int row = 4; row <= data; row++) {
                dp[row] = (dp[row-1] + dp[row-2] + dp[row-3]) % div;
            }
            
            long sum = dp[data];
            System.out.println(sum);
        }
 
        sc.close();
    }
}
 
  

 

 

5. 느낀점 또는 개선사항

처음에는 점화식 문제 1도 못건드렸는데, 계속 문제를 풀다보니 규칙성을 하나씩 찾을 수 있는 것 같다.

하지마, 아직 재귀함수 형태로 코드 작성하는 것에는 아직 어려움이 있다;

'Algorithm > Baekjoon' 카테고리의 다른 글

오르막수:11057번 - JAVA  (0) 2020.07.15
RGB거리 : 1149번 - JAVA  (0) 2020.07.15
합분해 : 2225번 - JAVA  (0) 2020.07.13
덱 :10866번 - JAVA  (0) 2020.07.10
오큰수 :17298번 - JAVA  (0) 2020.07.10
'Algorithm/Baekjoon' Related Articles more
Comments