[백준] 1, 2, 3 더하기 5 (★) (15990번 JAVA) / 400 - 다이나믹 프로그래밍 1

[백준] 1, 2, 3 더하기 5 (★) (15990번 JAVA) / 400 - 다이나믹 프로그래밍 1

---

[접근방법]

 

** [1, 2, 3 더하기] 시리즈에서 중요한 것은 N을 만들기 위해 사용할 수 있는 숫자는 1 , 2 , 3 뿐이라는 것이다.

 

이 당연한 말이 뭐가 중요한가 싶겠지만,

사용 가능한 숫자가 1, 2, 3 뿐이라는 것은 dp[N] 에 영향을 줄 수 있는 원소들은

dp[N - 1] , dp[N - 2], dp[N - 3] 뿐이라는 것이다.따라서 점화식 dp[N]은 dp[N - 1] , dp[N - 2], dp[N - 3]을 이용하여 만들어진다.

 

N을 만들 수 있는 방법 수를 저장한 배열인 dp[]는 2차원 배열로 구성된다.

dp[i][1] : 합이 i 가 되는 수식이 '1' 로 끝나는 경우의 수

dp[i][2] : 합이 i 가 되는 수식이 '2' 로 끝나는 경우의 수

dp[i][3] : 합이 i 가 되는 수식이 '3' 로 끝나는 경우의 수

 

EX) dp[6] 구하기

dp[3] 경우의 수 : (3) , (1 + 2) , (2 + 1)

dp[4] 경우의 수 : (1 + 3) , (3 + 1) , (1 + 2 + 1)

dp[5] 경우의 수 : (1 + 3 + 1) , (2 + 1 + 2) , (2 + 3) , (3 + 2)

 

3의 경우의 수 중 수식의 마지막이 3인 경우 : (3)

5의 경우의 수 중 수식의 마지막이 1인 경우 : (1 + 3 + 1)

 

따라서, dp[6] = 8 이다.

 

이 수식을 이용해 구해지는 점화식은

dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % 1,000,000,009

dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % 1,000,000,009

dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1,000,000,009

로, 도출된다.

 

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{

    public static long[][] dp;
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        dp = new long[100_001][4];
        dp[1][1] = 1; // 1
        dp[2][2] = 1; // 2
        dp[3][1] = 1; // 2 + 1
        dp[3][2] = 1; // 1 + 2
        dp[3][3] = 1; // 3

        // 미리 dp[] 채워 놓기
        for (int i = 4; i<=100_000; i++){
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % 1_000_000_009;
            dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % 1_000_000_009;
            dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % 1_000_000_009;
        }

        for(int i=0; i<T; i++){
            int N = Integer.parseInt(br.readLine());
            bw.write((dp[N][1] + dp[N][2] + dp[N][3]) % 1_000_000_009 + "\n");
        }

        bw.flush();
        bw.close();
    }


}

---

[ 2회차 풀이 (1/28) ]

[접근 방법]

- 1회차 풀이와 같다.

 

실행 시간 1초 = 약 2000만번 연산

N의 범위 (1 ≤ N ≤ 100,000)
O(N^2) = 10만 * 10만 = 100억 (불가)
O(NlogN) = 10만 * 5 = 50만 (가능)

 

[JAVA 코드]

// 15990 - 1, 2, 3 더하기 5
import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        
        // 끝자리가 1, 2, 3인 각각의 방법 수
        long[][] DP = new long[100_001][4];
        DP[1][1] = 1; // 1
        DP[2][2] = 1; // 2
        DP[3][1] = 1; // 2+1
        DP[3][2] = 1; // 1+2
        DP[3][3] = 1; // 3

        /*
         * N을 합으로 하는 경우
         * = 마지막 수가 1인 경우 + 마지막 수가 2인 경우 + 마지막 수가 3인 경우
         * 마지막 수가 1인 경우 = (N-1을 합으로 하고 마지막이 2인 경우) + (N-1을 합으로 하고 마지막이 3인 경우)
         * 마지막 수가 2인 경우 = (N-2을 합으로 하고 마지막이 1인 경우) + (N-2을 합으로 하고 마지막이 3인 경우)
         * 마지막 수가 3인 경우 = (N-3을 합으로 하고 마지막이 1인 경우) + (N-3을 합으로 하고 마지막이 2인 경우)
        */

        for(int i=4; i<=100_000; i++){
            DP[i][1] = (DP[i-1][2] + DP[i-1][3]) % 1_000_000_009;
            DP[i][2] = (DP[i-2][1] + DP[i-2][3]) % 1_000_000_009;;
            DP[i][3] = (DP[i-3][1] + DP[i-3][2]) % 1_000_000_009;;
        }


        for(int i=0; i<T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write((DP[n][1] + DP[n][2] + DP[n][3]) % 1_000_000_009 + "\n");
        }

        bw.flush();
        
        bw.close();
        br.close();
    }
}


/*
실행 시간 1초 = 약 2000만번 연산

N의 범위 (1 ≤ N ≤ 100,000)
O(N^2) = 10만 * 10만 = 100억 (불가)
O(NlogN) = 10만 * 5 = 50만 (가능)
*/

 

[Rewind]

1. 어려웠던 점

- 정답을 1_000_000_009로 나누라는 것을 잊어버렸다.

- DP 배열의 자료형이 왜 long이여야 하는지 알지 못하였다.

 

2. 알게된 점

- 접해본 문제여서 쉽게 해결할 수 있었다.

- DP[i][1] + DP[i][2] + DP[i][3]이 30억을 넘을 수 있기 때문에 +-21억인 int형에 못들어 가는 것인가?

 

3. 해결 방안 

- 문제를 꼼꼼히 이해 해야한다.