[백준] 9095번 1, 2, 3 더하기

1. 문제

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

정수 n이 주어졌을 때, 1, 2, 3을 사용하여 n을 만들 수 있는 방법의 수를 구하는 문제이다. 단, 같은 숫자라도 순서가 다르면 다른 방법으로 간주한다.

예를 들어, 정수 4를 1, 2, 3의 합으로 나타내는 방법은 다음과 같이 7가지이다.

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

2. 풀이

이 문제는 동적 계획법(DP)을 이용해 해결할 수 있다.
n을 만드는 방법은 다음 세 가지 경우로 나뉜다.

1️⃣ 1을 마지막에 더하는 경우

• n-1을 만든 뒤, 마지막에 +1을 한다.
  -> 방법의 수는 dp[n-1]

2️⃣ 2를 마지막에 더하는 경우

• n-2를 만든 뒤, 마지막에 +2를 한다.
  -> 방법의 수는 dp[n-2]

3️⃣ 3을 마지막에 더하는 경우

• n-3을 만든 뒤, 마지막에 +3을 한다.
  -> 방법의 수는 dp[n-3]

따라서 점화식은 다음과 같이 표현할 수 있다.

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

🔑 코드

int[] dp = new int[11];

dp 배열은 n을 1, 2, 3의 합으로 나타내는 방법의 수를 저장한다.

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

기본값을 설정하고, 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]);
}

입력받은 테스트 케이스마다 결과를 출력한다.

3. 소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i=4; i<11; 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]);
        }
    }
}