백준 9095번: 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

이 문제는 조금 어려웠던 것 같다. 알고리즘 분류는 다이나믹 프로그래밍이다. 다이나믹 프로그래밍이란 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

 

1 = 1 (1개)

 

2 = 1 + 1

   = 2 (2개)

 

3 = 1 + 1 + 1

   = 1 + 2

   = 2 + 1

   = 3 (4개)

 

4 = 1 + 1 + 1 + 1 

   = 1 + 1 + 2

   = 1 + 2 + 1

   = 2 + 1 + 1

   = 2 + 2

   = 1 + 3

   = 3 + 1(7개)

 

n을 1, 2, 3으로 나타낼 수 있는 경우의 수를 S(n)이라고 하면 S(n) = S(n - 3) + S(n - 2) + S(n - 1)이라는 점화식을 얻을 수 있다.

4의 경우를 보면 {1을 1, 2, 3의 합으로 나타 낸 집합들에 3을 추가한거} + {2를 1, 2, 3의 합으로 나타 낸 집합들에 2를 추가한거} + {3을 1, 2, 3의 합으로 나타 낸 집합들에 1을 추가한거}와 같다. 

 

 

n은 11 이하 양수이므로 배열을 만들어 미리 담아둔 후 값을 입력받을 때 마다 StringBuilder에 추가해서 한번에 출력하였다. 

import java.util.*;
public class Main {
	public static void main(String[] args){
		int T, n;
		Scanner sc = new Scanner(System.in);
		T=sc.nextInt();
		
		int[] s = new int[12];
		s[1] = 1;
		s[2] = 2;
		s[3] = 4;
		
		for(int i=4; i<12; i++) {
			s[i] = s[i-1] + s[i-2] + s[i-3];
		}
		StringBuilder sb = new StringBuilder();
		int k;
		for(int i=0; i<T; i++) {
			k = sc.nextInt();
			sb.append(s[k]+"\n");
		}
		System.out.print(sb);
	}
}