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

1. 문제 링크 https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

2. 문제 

3. 문제 요약

 정수 N을 1, 2, 3을 이용해서 표현가능한 식의 갯수를 출력하라.

 

4. 문제 풀이

(1)  다이나믹 프로그래밍

  전형적인 다이나믹 프로그래밍 문제 중 하나다.

  앞에서 구한 값을 이용해 다음 값을 빠르게 계산하면 되는데,  (n) 은 앞에서 구한 값이라 할 때

  2= 1+(1)

  3= 2+(1), 1+(2)

  4= 3+(1), 2+(2), 1+(3)

  5= 4+(1), 3+(2), 2+(3)
이런식으로 진행하면 된다.

 

피보나치의 응용버전으로  F(n)  = F(n-1) + F(n-2) + F(n-3) 식을 이용해서 바로 구할 수 있다. 

 

5. 풀이 코드

public static void Problem9095(String[] args) throws Exception {
    int T = Integer.parseInt(br.readLine());
    int[] dp = new int[11];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i <= 10; i++)
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    while (T-- > 0){
        int N = Integer.parseInt(br.readLine());
        bw.write(dp[N]+"\n");
    }
    bw.flush();
}

 

+ 매일 한 문제씩 풀어서 업로드를 하려고 했는데, 점차 과제와 프로젝트들이 할 게 많아져서

 주말마다 올리는 걸로 변경 !