1,2,3 더하기 5

📍 문제 설명

💡 접근

N의 범위가 커서 브루트포스로는 시간초과 나는 문제

n이라는 숫자가 m으로 끝나는 방법의 수를 담을 2차원 배열을 사용해야한다.

 

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[4][1] = 2 (3+1, 1+2+1)

dp[4][3] = 1 (1+3)

 

dp[n][1]의 일 때

dp[n-1][1]은 연속된 숫자가 되므로 제외하고 dp[n-1][2],dp[n-1][3] 에서 구한 방법의 수를 더해준다.

dp[n][2]의 일 때

dp[n-2][2]은 연속된 숫자가 되므로 제외하고 dp[n-2][1],dp[n-2][3] 에서 구한 방법의 수를 더해준다.

dp[n][3]의 일 때

dp[n-3][3]은 연속된 숫자가 되므로 제외하고 dp[n-3][1],dp[n-3][2] 에서 구한 방법의 수를 더해준다.

 

dp[4][1] = dp[3][2](2+1+2) + dp[3][3](1+3) = 2

dp[4][2] = dp[2][1] + dp[2][3] = 0

dp[4][3] = dp[1][1](1+3) + dp[1][2] = 1 이 되는것이다.

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, answer;
    static int[][] board;
    static long[][] arr, dp = new long[100001][4];
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //int t = kb.nextInt();
        int t = Integer.parseInt(br.readLine());
        T.solution();
        for(int i = 0; i < t; i++) {
            //n = kb.nextInt();
            n = Integer.parseInt(br.readLine());
            //dp[n][m]은 n이라는 숫자가 m으로 끝나는 방법의 수
            long cnt = (dp[n][1]+ dp[n][2] + dp[n][3]) % 1000000009;
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }

    private void solution() {
        dp[1][1] = 1;
        dp[2][2] = 1;
        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;
        }
    }

}