[백준] 9095번 : 1, 2, 3 더하기 [C/C++]

#문제

9095번: 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

---

#접근방법

동적계획법으로 접근하였다.

반응형

---

#풀이

#include <stdio.h>

int dp[11]={1,2,4};

int main(){
    int t,n;

    for(int i=3;i<11;i++)
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

    scanf("%d",&t);

    while(t--){
        scanf("%d",&n);

        printf("%d\n",dp[n-1]);
    }

    return 0;
}

 

정수n이 주어졌을 때 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.

 

n이 4일때 까지 경우의수를 구해보겠다.

 

n = 1 일 때

1

 

n = 2 일 때

1 1

2

 

n = 3 일 때

1 1 1

1 2

2 1

3

 

n = 4 일 때

1 1 1 1

1 1 2

1 2 1

2 1 1

1 3

2 2

3 1

 

1, 2, 4, 7개의 경우의 수로 나타난다. 뭔가 규칙이 있는 것 같다.

 

1,2,3으로만 합이 구성되므로 n = 4 일 때 경우의 수는 n = 3인 경우의 수에서 +1을 하고, n = 2인 경우의 수에서 +2를 하고, n = 1인 경우에서 +3을 하면 구할 수 있다.

 

이를 식으로 옮기면 dp[i] = dp[i-3] + dp[i-2] + dp[i-1]이 된다.

 

문제에서 n이 11까지만 들어온다고 하므로 n = 11까지 경우의 수를 미리 구해놓고 n을 입력 받을 때 마다 dp[n-1]을 출력하면 정답이다.

---

#성능

---

#정리

규칙을 발견하고 이를 식으로 옮길 수 있으면 풀 수 있는 문제였다.