[백준_9095번] 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

[문제]

 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

 

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

[코드]

import java.util.*;

public class BaekJoon_9095 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int testcase=sc.nextInt();
		
		while(testcase-->0) {
			int n=sc.nextInt();
			
			System.out.println(dynamic(n));
		}
	}
	
	/*
	 * n번째의 개수는 n-1 + n+2 + n-3의 개수들을 더한 값과 닽다
	 * 따라서 dynamic(n-3)+dynamic(n-2)+dynamic(n-1)이 오류가 없기 위해서는
	 * n이 1,2,3일 떄 값을 구해 return 시키고 이외의 값을 재귀호출을 통해 구한다.
	 */
	public static int dynamic(int n) {
		if(n==0)
			return 0;
		if(n==1)
			return 1;
		if(n==2)
			return 2;
		if(n==3)
			return 4;
		
		return dynamic(n-3)+dynamic(n-2)+dynamic(n-1);
	}
}

 

[고찰]

 이번 문제는 백트래킹으로 접근을 해보면서 어떻게 풀어야하나 고민을 많이 해봤지만 도저히 생각이 나질 않아 다른 사람의 코드를 참고했다. 결론은 백트래킹이 아닌 다이나믹 프로그래밍(동적 계획법)을 사용하는 문제였다. 규칙은 아주 간단했는데 n번째의 개수는 n-3 + n-2 + n-1의 개수를 합한 값이 된다. 해답을 보면 아주 간단하게 느껴지지만 이러한 규칙을 스스로 찾는 방법과 어떤 알고리즘을 사용해서 풀어야하는지는 아직 어렵게만 느껴진다.