-극장좌석(3202)-

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

2302번: 극장 좌석

 

풀이 :

#include <iostream>
using namespace std;
 
int n, m;
int sit[41];
 
void makesit() {
    sit[0] = 1;
    sit[1] = 1;
    sit[2] = 2;
 
    for(int i = 3; i <= 40; i++) {
        sit[i] = sit[i-2] + sit[i-1];
    }
    return;
}
 
int main() {
    cin >> n;
    cin >> m;
    int answer = 1;
    int pres_vip = 0;
    int prev_vip = 0;
    
    makesit();
    
    while(m--) {
        cin >> pres_vip;
        answer *= sit[pres_vip - prev_vip - 1];
        prev_vip = pres_vip;
    }
    answer *= sit[n-prev_vip];
    cout << answer << endl;
 

처음에 너무 어렵게 풀려고 했었다. 기계적으로 동적계획법을 사용한 대입방법을 작성하던 도중 시간이 너무 많이 걸리고

정말 이렇게 푸는게 해답이 아니라고 생각하여 다시 처음부터 생각하였다.

너무 깊숙히 생각하는 문제는 아니고, 하나씩 경우의 수를 찾아가면서 수의 규칙을 파악하는 문제였다.(피보나치)

너무 어렵게 풀려하지 말자 제발

 

가장 작은 입력부터 큰 입력까지 포괄하는 알고리즘을 만든다고 생각하고 접근하자.

이정도로 생각하면 되겠지보다는 완벽하게 하자