[2302] 극장좌석 - c++

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

2302번: 극장 좌석

정말 미세하게 DP에 대한 감이 잡히기 시작한 것 같다. DP문제라는 것을 알고 풀긴 했지만! 점화식을 찾아냈다는 것이 뿌듯했다.

하지만 점화식을 찾아낸 것 그뿐이고 그다음을 어떻게 해야 할지 몰라 답을 찾아서 봤다....ㅎ

---

풀이

먼저 점화식을 찾아낸 방법은

하나하나 다 써봤다. 이것만큼 좋은 게 있을까?

$$\Large d[i] \space =\space d[i-1] \space + \space d[i-2]$$

d [i]는 i개의 수가 있을 때의 경우의 수 임을 알 수 있다.

그럼 이걸 어떻게 사용 하느냐의 문제다!

내가 본 풀이에서는

vip좌석의 왼쪽에 있는 좌석의 수를 계산하는 식으로 답을 구해 나갔다

위 말만 들으면 어려우니 쉽게 그림으로 설명하면

위처럼 답을 구할 수 있는 것이다!!

---

CODE

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, m;
int arr[45];
long long dp[45] = {1,1,2,3};

int main(){
  init();
  cin >> n >> m;
  for(int i = 4; i <= n; ++i) dp[i] = dp[i-1] + dp[i-2];
  int idx = 1, ans = 1;
  while(m--){
    int vip;
    cin >> vip;
    ans *= dp[vip - idx];
    idx = vip + 1;
  }
  ans *= dp[(n+1) - idx];
  cout << ans;

  return 0;
}

---

문제를 풀며

DP문제는 고민 시간을 30분 넘으면 답을 보기로 하고 문제를 푼다.
이 문제도 딱 30분이 되었을 때 답을 봤다.

왜 저 아이디어를 생각 못했을까 싶다. 하지만 못 푼 건 못 푼 거니깐
아이디어를 배운다는 마인드로 가자 화이텡

더 열심히 해서 DP마스터가 되고 싶다.