백준 9095번: 1, 2, 3 더하기

 

이 문제는 다이나믹 프로그래밍을 이용하여 풀 수 있다.

dp 1차원 배열을 생성하고, dp[n] 는 정수 n을 1,2,3 의 합으로 나타낼 수 있는 경우의 수를 의미한다.

 

dp[1] 은 1로만 나타낼 수 있으므로 1가지이다.

 

n = 1 일 때,
1
한 가지이므로 dp[1] = 1 이다.

n = 2 일 때,
1 + 1
2
두 가지이므로 dp[2] = 2 이다.

n = 3 일 때,
1 + 1 + 1
2 + 1
1 + 2
3
총 4가지이므로 dp[3] = 4 이다.

n = 4 일 때,
1 + 1 + 1 +1
2 + 1 + 1
1 + 2 + 1
3 + 1
1 + 1 + 2
2 + 2
1 + 3
총 7가지이므로 dp[4] = 7 이다.

그런데 n = 4 인 경우의 수에서 아래의 빨간색 부분의 연산은 dp[3]에 포함된 경우의 수와 같다.
1 + 1 + 1 +1
2 + 1 + 1
1 + 2 + 1
3 + 1

아래의 파란색 부분의 연산 역시 dp[2]에 포함된 경우의 수와 동일하다.
1 + 1 + 2
2 + 2

아래의 초록색 부분의 연산은 dp[1]에 포함된 경우의 수이다.
1 + 3

즉, dp[4] 는 결국 dp[3] + dp[2] + dp[1]을 더한 것과 같다.

---

마찬가지로 n = 5 일 때는

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

13가지로 dp[5] = 13이다. 그런데 아래의 빨간색 부분의 연산은 dp[4]에 포함된 경우의 수와 같다.

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

아래의 파란색 부분의 역시은 dp[3]에 포함된 경우의 수와 같다.
1 + 1 + 1 + 2
2 + 1 + 2
1 + 2 + 2
3 + 2

아래의 초록색 부분의 연산 역시 dp[2]에 포함된 경우의 수와 동일하다.
1 + 1 + 3
2 + 3

dp[1]에 4를 더하는 경우는 주어진 1,2,3을 초과하는 '4'를 활용하기 때문에 경우의 수에 포함할 수 없다.

dp[5] 는 결국 dp[4] + dp[3] + dp[2]를 더한 것과 같다.

 

여기서 얻을 수 있는 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이 된다.

점화식을 얻었으니 이를 이용하여 dp의 값들을 구할 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		for (int t = 0; t < T; t++) {
			int n = Integer.parseInt(br.readLine());
			int[] dp = new int[11];

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

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

			bw.write(dp[n] + "\n");
		}
		bw.flush();
	}
}

 

참고

https://lotuslee.tistory.com/43

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