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

설명

DP로 풀이하는 경우
점화식을 찾는다.

합이 1인 경우
- 1 
=> 1가지

합이 2인 경우
- 1,1
- 2
=> (1+1)가지 = 2가지

합이 3인 경우
- 1,1,1
- 1,2 -> 2가지 
- 3
=> (1+2+1)가지 = 4가지

합이 4인 경우
- 1,1,1,1
- 1,1,2 -> 3가지
- 1,3 -> 2가지
- 2,2 -> 1가지
=> (1+3+2+1)가지 = 7가지

합이 5인 경우
- 1,1,1,1
- 1,1,1,2 -> 4가지
- 1,2,2 -> 3가지
- 1,1,3 -> 3가지
- 3,2 -> 2가지
=> (1+4+3+3+2) = 13가지

확인해보면 a[n] = a[n-1] + a[n-2] + a[n-3]이라는 점화식을 갖는다.

일단 DP를 생각했을 때, 경우의 수에 대한 기본값은 위에서 풀이한 것 바탕으로 a[1] = 1, a[2] = 2, a[3] = 4 이다.

만약 N = 4라면,
이는 1+a[3], 2+a[2], 3+a[1]이 된다.

만약 N = 5라면,
1+a[4], 2+a[3], 3+a[2]가 나온다.

따라서 이전에 만든 수에서 1,2,3을 더했을 때 현재의 수가 나오니 현재의 수가 나오는 각각의 이전 조합의 경우의 수를 더한다.

백트래킹으로 풀이하는 경우
0부터 1,2,3을 더해서 구해지는 결과에 1,2,3을 반복적으로 더하는 과정을 n에 도달할 때까지 반복한다.

코드

DP

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class P9095 {
    static int T;
    static int dp[];

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

        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());
        dp = new int[11];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

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

            dp(dpSize);
            sb.append(dp[dpSize]);
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static void dp(int max) {
        for (int i = 4; i <= max; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
    }
}

재귀

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class P9095 {
    static int T;
    static int count;

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

        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            count = 0;
            findCaseNum(0, Integer.parseInt(br.readLine()));

            sb.append(count);
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static void findCaseNum(int now, int goal) {
        if (now > goal) {
            return;
        }
        else if (now == goal) {
            count += 1;
            return;
        } else {
            for (int i = 1; i <= 3; i++) {
                findCaseNum(now + i, goal);
            }
        }
    }
}

Reference

• https://jyami.tistory.com/15
• https://sihyungyou.github.io/baekjoon-9095/