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

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

15989번: 1, 2, 3 더하기 4

 

풀면서 이거 골드문제 같은데?! 했는데 실버였다. (어려운만큼 내 실력이 부족하다는거겠지)

 

사실 풀고 나서는 실버라는게 수긍이 갔던 문제..! 

모든 DP문제가 그렇듯이 점화식만 깨우치면 쉽다..!

 

문제를 읽자마자 DP 문제라는 것을 알 수 있는데, 저번에 풀었던 동전 문제와 비슷했다.

※ 백준2293 https://smile-development.tistory.com/87

 

문제에서 중요한 건 순서가 달라도 사용 개수가 같으면 다른 경우로 생각 안 함

예) 1 + 1 + 2 + 3 은 3 + 1 + 2 + 1 이랑 같음

 

나는 모든 경우를 오름차순으로 생각했다 (1 사용 > 2 사용 > 3 사용 이렇게)

1 + 1 + 2 + 3 // 1 + 2 + 3 + 3 // 2 + 2 + 3 + 3 → OK

2 + 3 + 1 + 1 // 3 + 2 + 2 → NO

 

[사용한 방식]

※ DP구성 : DP[합계][마지막에 오는 숫자]

- 마지막에 오는 숫자가 1이면 이전 숫자는 1만 된다.

- 마지막에 오는 숫자가 2이면, 이전 숫자는 1,2만 된다.

- 마지막에 오는 숫자가 3이면, 이전 숫자는 1, 2, 3이 된다.

 

※ N을 이루는 경우의 수 : (1) + (2) + (3)

(1) DP[N-1][1]

(2) DP[N-2][1] + DP[N-2][2]

(3) DP[N-3][1] + DP[N-3][2] + DP[N-3][3]

 

태블릿으로 끄적끄적한 관계식

 

[코드]

package BOJ;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class boj15989 {
	private static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		
		int maxNum = 0;
		ArrayList<Integer> arr = new ArrayList<>();
		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(br.readLine());
			arr.add(num);
			maxNum = Math.max(maxNum, num);
		}
		
		dp = new int[maxNum+1][4];
		
		dp[1][1]=dp[2][1]=dp[3][1]=1;
		dp[2][2]=dp[3][3]=dp[3][2]=1;
		
		
		for(int i=4; i<=maxNum; i++) {
			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 : arr) {
			int sum = dp[i][1]+dp[i][2]+dp[i][3];
			bw.write(sum+"\n");
		}
		
		bw.flush();
		bw.close();
	}
}