다이나믹 - 1,2,3 더하기

문제

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

분석/설계

입력 숫자의 범위가 1~11이지만 다이나믹 프로그래밍으로 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

N이 1, 2, 3 의 경우 점화식 적용할 경우 index가 음수 값이거나 0이기 때문에

따로 정의 해줬습니다.

 

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

구현 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		int N[] = new int[T];
		int dp[] = new int[11];
		
		for(int i=0; i<T; i++) {
			N[i] = scanner.nextInt();
		}
		
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		
		for(int i=0; i<N.length; i++) {
			for(int j=3; j<N[i]+1; j++) {
				dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
			}	
		}
		
		for(int i=0; i<N.length; i++) {
			System.out.println(dp[N[i]]);
		}

		scanner.close();
	}
}

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고, 문제만 보고 점화식이 잘 정의가 안되면

예시를 여러 개 만들고 패턴을 찾아내어 점화식을 만들고 알고리즘을 적용하여 코드를 작성하면 

수월합니다.

참고

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