[BOJ] 2302번 : 극장 좌석(C++)

김영한·2021년 4월 6일
0

알고리즘

목록 보기
38/74

문제 링크 : 백준 2302번

[문제 접근]

DP를 이용해 풀었다.
VIP석을 기준으로 나올 수 있는 방법의 가짓수를 곱해주면 된다.
ex) 1 2 3 4 5 6 7 8 9 에서 VIP석은 4, 7이라고 했을 때
(1,2,3 에서 나올 수 있는 방법 수) X (5,6 에서 나올 수 있는 방법 수) X (8,9 에서 나올 수 있는 방법 수) 가 정답이다.

  1. 구해야하는 좌석의 개수당 나올 수 있는 방법의 수는 피보나치 수열과 같으므로 dp에 값을 저장해둔다.
    • 1,2,3에서 나올 수 있는 방법의 수는 좌석의 개수가 3개이므로 dp[3]에 저장되어있다.
  2. 입력받는 VIP석에 따라서 방법의 수를 계산해 ans에 곱해주면 된다.

[소스 코드]

#include <iostream>
#include <algorithm>

using namespace std;
int n, m;
int dp[41];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int now = 0;
    int ans = 1;
    dp[0] = 1;
    dp[1] = 1;
    for(int i=2 ; i<=40 ; i++) {
        dp[i] = dp[i-1]+dp[i-2];
    }
    for(int i=0 ; i<m ; i++) {
        int a;
        cin >> a;
        int num = (a-now)-1;
        ans *= dp[num];
        now = a;
    }
    ans *= dp[n-now];
    cout << ans << "\n";
}

0개의 댓글