백준 2302번 극장 좌석

문제 링크입니다: https://www.acmicpc.net/problem/2302

좌석 수 별로 경우의 수를 구하다 보면 간단히 피보나치 수열인 것을 확인할 수 있다.

피보나치 수열인 이유는 

1. i번째 좌석에 i번 티켓을 가진 사람이 앉게 된다면 i-1개의 좌석의 경우의 수가 되고

2. i번째 좌석에 i-1번 티켓을 가진 사람이 앉게 된다면 i-1번 좌석에는 i번 티켓을 가진 사람이 앉게 되므로 i-2개의 좌석의 경우의 수가 된다.

따라서 VIP 좌석이 있다면 0~첫번째 VIP 좌석 사이에 있는 좌석의 수번째 피보나치 수열, 첫번째 VIP 좌석과 두번째 VIP 좌석 사이에 있는 좌석의 수번째 피보나치 수열, ..., i번째 VIP 좌석과 i+1번째 VIP 좌석 사이에 있는 좌석의 수번째 피보나치 수열을 모두 곱하면 답을 구할 수 있습니다.

물론 VIP 좌석이 없다면 답은 N번째 피보나치 수열입니다.

#include <iostream>

using namespace std;

 

const int MAX = 40;

 

int N, vipNum;

int cache[MAX + 1];

int VIP[MAX + 1];

 

//피보나치

void preCalculate(void)

{

        cache[0] = cache[1] = 1;

        //cache[i-1]: i가 제자리에 앉을 경우

        //cache[i-2]: i가 움직일 경우 -> i는 i-1에 i-1은 i에 앉아야함

        for (int i = 2; i <= N; i++)

               cache[i] = cache[i - 1] + cache[i - 2];

}

 

int numOfWays(void)

{

        int result = 1;

        for (int i = 1; i <= vipNum; i++)

               //경우의 수들을 곱한다

               result *= cache[VIP[i] - VIP[i - 1] - 1]; //VIP 지정석 이전까지의 좌석 수

        return result *= cache[N - VIP[vipNum]];

}

 

int main(void)

{

        cin >> N;

        if (N < 1 || N>MAX)

               exit(-1);

 

        preCalculate();

 

        cin >> vipNum;

        int result = 1;

        for (int i = 1; i <= vipNum; i++)

        {

               int reserved;

               cin >> reserved;

               VIP[i] = reserved;

        }

        cout << numOfWays() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~