kingsubin

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

// # 1, 2, 3 더하기
public class boj_9095 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] dp = new int[11];

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());
        dp[1] = 1; dp[2] = 2; dp[3] = 4;

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

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
}

- dp는 쪼개고 점화식 ! 

 

- n을 1, 2, 3을 더해서 만드는 방법의 수

- x + x + x + .... ? = n -> 여기서 ? 자리에 올 수 있는 수는 1, 2,3 밖에 없다.

- 1이 왔을 경우 dp[n-1]

- 2가 왔을 경우 dp[n-2]

- 3이 왔을 경우 dp[n-3]

 

- ex 4

- 마지막이 1이 라는 것은 3을 만드는 경우의 수에 마지막에 1을 붙인것과 같음 -> dp[3]

- 마지막이 2라는 것은 2를 만드는 경우의 수에 마지막에 2를 붙인것과 같음 -> dp[2]

- 3이라는 것은 1을 만드는 경우의 수에 마지막에 3을 붙인것과 같음 -> dp[1]

 

- dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

 

 

import java.io.*;
 
public class boj_9095 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int k = Integer.parseInt(br.readLine());
            System.out.println(go(0, k));
        }
    }
 
    static int go(int sum, int goal) {
        if (sum > goal) return 0;
        if (sum == goal) return 1;
        int now = 0;
        for (int i = 1; i <= 3; i++) {
            now += go(sum + i, goal);
        }
        return now;
    }
}
 

 

- 20.12.01 추가

- 재귀

 

- 재귀를 이용해서 다시 풀이

 

 

 

 

---

www.acmicpc.net/problem/9095