[BOJ] 2302번 : 극장 좌석

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;

int d[42]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	d[0] = 1, d[1] = 1, d[2] = 2; 
	for (int i = 3; i <= 40; i++) {
		d[i] = d[i - 1] + d[i - 2]; 
	}

	int n, m;
	cin >> n;
	cin >> m; 
	int ans = 1;
	int start_idx = 1;
	while (m--) {
		int x;
		cin >> x; 
		ans *= d[x - start_idx]; 
		start_idx = x + 1;
	}
	ans *= d[n - start_idx + 1];
	cout << ans << '\n';
}

dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d[i] = i명일 때의 가짓수 ( 지정석이 없을 때) 

2. 점화식을 작성한다. d[i] = d [i-1] + d [i-2] ( i >= 3) 

3. 초기값을 설정한다. d[0] , d [1]  = 1, d [2] = 2  

d [0] = 1로 설정해야 하는 이유는 지정석이 연속해서 있을 때, 값이 0으로 출력되는 것을 방지하기 위함이다. 

 

3. solution 2 :

// Authored by : sukam09
// Co-authored by : -
// http://boj.kr/d6fbad043aa84210b49531fc17c48ef2
#include <bits/stdc++.h>
using namespace std;

vector<int> v = {0}; // 고정석의 번호
int d[45]; // 연속된 자리의 개수가 i개일 때 앉을 수 있는 경우의 수

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int n, m, vv;
  cin >> n;
  cin >> m;
  while (m--) {
    cin >> vv;
    v.push_back(vv);
  }
  v.push_back(n + 1);

  d[0] = 1;
  d[1] = 1;
  d[2] = 2;
  for (int i = 3; i <= n; i++) d[i] = d[i - 1] + d[i - 2];

  int ans = 1;
  for (int i = 1; i < v.size(); i++) ans *= d[v[i] - v[i - 1] - 1];
  cout << ans; 
}
/*
앉을 수 있는 경우의 수는 마지막 자리에 i번이 앉거나 마지막에서 두번째 자리부터 차례대로
i번과 i - 1번이 앉는 두 가지 경우밖에 없으므로 d[i] = d[i - 1] + d[i - 2]이 되어 피보나치 수열을 이룸
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2302.cpp

basic-algo-lecture/0x10/solutions/2302.cpp at master · encrypted-def/basic-algo-lecture