본문 바로가기
[C++] 알고리즘 교육/16. 동적계획법1

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

by 안산학생 2019. 8. 12.

문제


숫자 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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}

댓글