[백준] 9095: 1, 2, 3 더하기

'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보다 작다.

예시 -
3
4
7
10

👉출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예시 -
7
44
274

---

✍내 풀이

import java.util.*;

public class Main {

	static int[] arr = new int[12];
	
	public static void main(String[] args) {
		arr[0] = 1;
		arr[1] = 1;
		arr[2] = 2;
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		for( int i = 0 ; i < n ; i++) {
			int temp = sc.nextInt();
			System.out.println(sum123(temp));
		}
	}
	
	static int sum123(int n) {
		if( n >=3 ) {
			arr[n] = sum123(n-1) + sum123(n-2) + sum123(n-3);
		}
		
		return arr[n];
	}
}

---

✍Note

만약 n이 5일때, n이 4일때의 경우에서 뒤에 1을 더하고, n이 3일때의 경우에서 뒤에 2를 더하고, n이 2일때의 경우에서 뒤에 3을 더하는 구조로 생각해보았다.
더하는 방향을 한방향으로 생각하니 겹치는 경우 없이 간단하게 해결되었다.
점화식은 arr[n] = arr[n-1] + arr[n-2] + arr[n-3] 꼴이다.

동적계획법의 top-down방식으로 풀었다.