BOJ 15989 - 1,2,3 더하기 4

15989번: 1, 2, 3 더하기 4

 

정수 n을 1, 2, 3의 합으로 나타내는 방법을 구해라.

n ≤ 10,000

재귀를 통해 모든 것을 확인하기에는 너무 많다.

숫자가 1, 2, 3이니 합을 표현할 때 1, 2, 3으로 끝나는 경우를 나눠보자.

2차원 배열로 dp를 하자.

int [][] dp; → dp [i][j]는 i를 만들 때 마지막 수가 j인 경우를 이야기한다.

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

public class Main {

    static FastReader scan = new FastReader();

    public static void main(String[] args) {
        int T = scan.nextInt();
        int[][] dp = new int[10002][4];
        dp[1][1] = 1;
        dp[2][1] = 1;
        dp[2][2] = 1;
        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;

        for (int i = 4; i <= 10000; i++) {
            dp[i][1] = 1;
            dp[i][2] = dp[i-2][1] + dp[i-2][2];
            dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3];
        }

        for (int p = 0; p < T; p++) {
            int N = scan.nextInt();
            System.out.println(dp[N][1] + dp[N][2] + dp[N][3]);
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}