#include <iostream> using namespace std; int main() { int N, M; cin >> N >> M;
int vip[41]={0}; int dp[41]={0}; int ans=1; for(int i=1; i<=M; i++) cin >> vip[i];
dp[0]=1; dp[1]=1; dp[2]=2; for(int i=3; i<=N; i++) dp[i]=dp[i-1]+dp[i-2]; //vip가 0명일때 기준으로 값을 저장, 피보나치 수열
vip[M+1]=N+1; // 임의로 M+1번째로 고정해준다. 계산하기위해 for(int i=1; i<=M+1; i++) //1~vip[1]-1 , vip[1]+1~vip[2]-1], vip[2]+1~N, M+1개의 구간 { int k=0; for(int j=vip[i-1]+1; j<vip[i]; j++) k++; //자리수 카운트 ans= ans*dp[k]; } //값을 곱해준다. 각 vip 사이의 좌석수만큼의 경우의 수들을 곱한 것이 답.
cout << ans; } |
'알고리즘 문제 풀이 > 1DP_과제(~180615)' 카테고리의 다른 글
171023_2490_윷놀이 (0) | 2017.10.23 |
---|---|
171022_NUMB3RS_두니발 박사의 탈옥 (0) | 2017.10.22 |
171020_11048_이동하기 (0) | 2017.10.20 |
171019_1699_제곱수의 합 (0) | 2017.10.19 |
171018_p를 출력하는 프로그램 p (0) | 2017.10.18 |