[실버 3] 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

풀기 전:

 

dp [i]의 정의를 숫자 1, 2, 3 중에 i개 사용 한 거라고 정의하면

n은 최대 10 이므로

dp [10]까지 구하면 모든 경우의 수는 구하고

그다음 dp [10]까지 N이 몇 개 인지 세주면 되나?

 

푼 후:

되네

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T;
        int n;

        T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            n = Integer.parseInt(br.readLine());

무난하게 입력받고

            ArrayList<ArrayList<Integer>> dp = new ArrayList();
            ArrayList<Integer> tmp;
            int count = 0;

            for (int i = 0; i <= n; i++) {
                tmp = new ArrayList<>();
                dp.add(tmp);
            }

            dp.get(0).add(0);

            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < dp.get(i - 1).size(); j++) {
                    dp.get(i).add(dp.get(i - 1).get(j) + 1);
                    dp.get(i).add(dp.get(i - 1).get(j) + 2);
                    dp.get(i).add(dp.get(i - 1).get(j) + 3);
                }
            }

            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < dp.get(i).size(); j++)
                    if (dp.get(i).get(j) == n) count++;
            }

            sb.append(count + " ");
            System.out.println(sb);
            sb.setLength(0);
        }

    }
}

dp [i]는 dp [i-1]의 각각마다 +1 +2 +3을 저장한다