Algorithm, boj, 1,2,3더하기(9095)

풀이

• 1,2,3의 합으로 나타낼수 있고 숫자 하나이상 사용해야 한다
• 4 = 1+3, 2+3, 3+1, 4+0 (x)
• 이므로 dp[3] + dp[3] + dp[1]
• 5 = 1+4, 2+3, 3+2, 4+1, 5(x)
• 이므로 4를 나타낼수 있는 방법은 dp[4], 3을 나타낼수 있는 방법 dp[3]….. 따라서 dp[5] = dp[4]+dp[3]+dp[2]
• 이와 같은 규칙으로 점화식 도출이 가능하다.

package org.baekjoon;

import java.util.Scanner;

public class test9095 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int testCase = sc.nextInt();
		int[] answer = new int[testCase];
		int[] dp = new int[12];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;

		int idx=0;
		while (testCase != 0) {
			int num = sc.nextInt();
			for (int i = 4; i <= num; i++)
				dp[i] = dp[i-1]+dp[i-2]+dp[i-3];

			answer[idx++] = dp[num];
			--testCase;
		}
		for(int e:answer)
			System.out.println(e);

	}
}

---

Reference

• 문제보러가기

---