[Algorithm]Baekjoon 2302번 :: 극장 좌석

https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

 
 
 
int n, m, fixedSeatPositions;
int dp[41] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
 
    for (int i = 3; i <= n; ++i)
    {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    
    int start = 1;
    int answer = 1;
    vector<int> answers;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> fixedSeatPositions;
        
        answers.push_back(dp[fixedSeatPositions - start]);
        start = fixedSeatPositions + 1;
    }
    
    answers.push_back(dp[n + 1 - start]);
 
    for (int i = 0; i < answers.size(); ++i)
    {
        answer *= answers[i];
    }
 
    cout << answer;
}

 

일반석이 n개만큼 연속됐을 때, 경우의 수가 몇가지가 나오는지만 알면 풀 수 있는 문제이다.

물론 나는 풀지 못해서... 다른 사람 풀이를 봤다.

결론적으로는 피보나치수열규칙이랑 같았다.

 

규칙을 알았다면, 고정석기준으로 각 구간을 나눠서 각각의 구간마다 경우의 수를 구한다음, 마지막에 다 곱해주면 되었다.