[알고리즘 16.1.1] 동적계획법 - 숫자만들기

문제

---

숫자 1, 2, 3을 이용하여 숫자 N을 만드는 경우의 수를 출력하는 프로그램을 작성하시오. 예를 들어, N이 4일 경우에는 다음의 7가지 경우가 존재한다. 단, 경우의 수가 매우 많을 수 있으므로, 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

 

입력

---

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 )  

출력

---

1, 2, 3을 이용하여 N을 만들 수 있는 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.  

예제 입력

4

예제 출력

7

 

예제 입력

200

예제 출력

290816

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include<iostream>
 
using namespace std;
 
int n;
int arr[100005] = {0,};
 
int main(){
  
  cin>>n;
  
  arr[0] = 0;
  arr[1] = 1;
  arr[2] = 2;
  arr[3] = 4;
  
  long long int sum;
  for(int i=4; i<=n; i++){
    sum = arr[i-3] + arr[i-2] + arr[i-1];
    sum %= 1000007;
    arr[i] = sum;
  }
  
  cout<<arr[n];
  
  
  return 0;
}