[9095] 1,2,3 더하기

🔗 문제 링크

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

🔍 문제 설명

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

⚠️ 제한사항

• n은 양수이며 11보다 작다.

---

🗝 풀이 (언어 : Java)

DP로 푸는 문제이다. 4를 예로들면, 1+3, 2+2, 3+1 등으로 표현할 수 있다. 각 케이스별 특징으로 마지막으로 더하는 수를 없애면, 각각 1,2,3을 구하는 경우의 수를 구하는 문제로 바뀐다. 그래서 4를 구하는 경우의 수는 (1이 되는 경우의 수 + 2가 되는 경우의 수 + 3이 되는 경우의 수)로 나타낼 수 있다. 1,2,3의 경우의 수는 손수 계산해주고, 4부터는 $DP[i] = DP[i-3] + DP[i-2] + DP[i-1]$ 점화식을 이용하여 풀면 된다.

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

class Main {
    private static StringBuilder findCases(int n, int[] cases) {
        StringBuilder answer = new StringBuilder();
        // DP를 위한 배열, 1,2,3을 만드는 경우의 수 넣기
        int[] dp = new int[11]; // 숫자는 1~10까지
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int c : cases) {
            for (int i = 4; i <= c; i++) { // 4부터 구하는 수까지 경우의 수 다 구해서 배열 채우기
                if (dp[i] == 0) // 이미 앞에서 구한 적있으면 계산 x
                    dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
            }
            answer.append(dp[c]).append('\n');
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] cases = new int[n];
        for (int i = 0; i < n; i++)
            cases[i] = Integer.parseInt(br.readLine());
        br.close();
        System.out.print(findCases(n, cases));
    }
}