(코테) 백준_9095_1, 2, 3 더하기

 

 

 

 

 

 

정답.

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

public class Main {

	static int T,N;
	static int[] dp;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new  BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		
        	dp = new int[11];
			dp[0] = 1;  // ex)  1
			dp[1] = 2;  // ex)  2   11 ,2 
			dp[2] = 4;  // ex)  3   1 1 1 ,1 2, 2 1 , 3
			for(int i=3;i<11;i++) {
				dp[i]=  dp[i-3] + dp[i-2] + dp[i-1]; 
			}			
        
		//N 개수 만큼 반복.
		while(T-- > 0) { 
			N=Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
			System.out.println(dp[N-1]);			
		}
	}
	

}

 

 

회고.

 

이번 문제를 통해 점화식의 본질적인 개념과 동적 계획법(DP)에서의 설계 방법을 명확히 이해할 수 있었다.

📌 핵심 개념

• 문제 조건은 {1, 2, 3}을 이용해서 정수 N을 만들 수 있는 모든 경우의 수를 구하는 것이었다.
• 단순히 재귀로 접근하면 중복 호출이 많아져 시간 초과가 발생하기 때문에, DP로 해결해야 했다.

📌 점화식 도출 과정

• dp[i]는 숫자 i를 만들 수 있는 모든 경우의 수를 의미한다.
• 이 값을 구하기 위해 마지막에 어떤 숫자를 붙였는지에 따라 나눠서 생각했다.

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

• dp[i-1]: i-1을 만들고 마지막에 +1을 붙인 경우의 수
• dp[i-2]: i-2를 만들고 마지막에 +2를 붙인 경우의 수
• dp[i-3]: i-3을 만들고 마지막에 +3을 붙인 경우의 수

→ 즉, i를 만들 수 있는 경우의 수는
바로 이전 3개의 결과를 기반으로 확장되는 누적 조합 방식이라는 점을 배웠다.

📌 초기값 설정의 중요성

• dp[1] = 1 → (1)
• dp[2] = 2 → (1+1, 2)
• dp[3] = 4 → (1+1+1, 1+2, 2+1, 3)

이처럼 기저 조건을 명확히 정의해두어야 점화식이 올바르게 동작한다는 점도 체감했다.