1, 2, 3 더하기

풀이

 나는 이 문제를 DFS, 완전 탐색으로 접근했다. n의 범위가 11까지로 매우 작아서 시간 복잡도가 O(T*3^10)로 문제는 풀 수 있다. 하지만 DP로 푸는게 O(N)이기 때문에 더 좋다.

dp[i] : i 값을 가지는 정수를 1, 2, 3의 합으로 나타내는 경우의 수
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

시간 복잡도 : O(T*3^n)

Java

import java.io.*;
public class Main {
    static int cnt, N;
    public static void DFS(int sum){
        for(int i=1; i<=3; i++){
            if(sum+i<N){
                DFS(sum+i);
            } else if (sum+i==N) {
                cnt++;
            }
        }
    }

    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());
        while (T-->0){
            N = Integer.parseInt(br.readLine());
            cnt = 0;
            DFS(0);
            bw.write(String.valueOf(cnt)+"\n");
        }

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