[Java] 백준 15989번: 1, 2, 3 더하기 4

[문제 바로 가기] - 1, 2, 3 더하기 4

💡 접근 방식

문제 보고 조합? DFS? 이러다가 알고리즘 분류를 봤는데 그놈의 DP였다 -.-

일단 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 치기 때문에 중복이 되어서는 안된다. 따라서 오름차순 정렬을 하면 된다!

합이 1이 되는 것 : 1
합이 2가 되는 것 : 1+1, 2
합이 3이 되는 것 : 1+1+1, 1+2, 3

2차원의 dp 배열에서 합이 n이 되고 가장 뒤에 오는 수가 a(1, 2, 3 중 하나)라면 dp[n][a]가 되는 것이다.
따라서 dp[1][1], dp[2][1], dp[2][2], dp[3][1], dp[3][2], dp[3][3]을 모두 1로 초기화 해준다. (위에 적어놓은 것들에 대입하면 이해하기 쉽다.)

이제 1, 2, 3으로 합이 n이 되는 경우의 수를 구할 때 n이 4라면 1+1+1+1, 1+1+2, 2+2, 1+3와 같이 4가지가 나온다.

1. dp[4][1]은 dp[3][1]과 같다. 1+1+1에 1을 더한 것이기 때문이다.
2. dp[4][2]는 dp[2][1]와 dp[2][2]와 같다. 1+1과 2에 2를 더한 것이기 때문이다.
3. dp[4][3]은 dp[1][1]과 같다. 1에 3을 더한 것이기 때문이다.

따라서 점화식은 다음과 같다.
dp[n][1] = dp[n - 1][1]
dp[n][2] = dp[n - 2][1] + dp[n - 2][2]
dp[n][3] = dp[n - 3][1] + dp[n - 3][2] + dp[n - 3][3]

dp[4][3]은 dp[1][1] + dp[1][2] + dp[1][3]과 같지만 dp[1][2]과 dp[1][3]은 0이므로 dp[1][1]과 같은 것이다.

장황한 설명이지만 https://velog.io/@jkh9615/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-15989-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-4-Java 이 분의 설명을 참고하면 더 이해하기 쉬울듯 하다.

---

풀이

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

/**
 * 백준 15989 1, 2, 3 더하기 4 
 * - 흠.. dp..
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		int T = Integer.parseInt(br.readLine());
		int[][] dp = new int[10001][4];
		dp[1][1] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
		
		for (int i = 4; i <= 10000; i++) {
			dp[i][1] = dp[i - 1][1];
			dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
			dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
		}
		
		for (int i = 0; i < T; i++) {
			int n = Integer.parseInt(br.readLine());
			sb.append(dp[n][1] + dp[n][2] + dp[n][3] + "\n");
		}
		
		System.out.println(sb);
	}
}