취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2302번 문제인 극장 좌석이다.
문제는 아래 링크를 확인하자.

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

vip들을 기준으로 구간을 끊었을 때 각 구간의 사람들이 앉을 수 있는 경우의 수는 피보나치 수와 관련이 있다는 점을 관찰하자. (직접 관계식을 세워 유도해도 좋다.)

위에서 쪼개진 각 구간에 대하여 앉을 수 있는 경우의 수를 곱해 답을 구하고 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int fib[41];
vector<int> vec;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	fib[0] = fib[1] = 1;
	for (int i = 2; i < 41; i++) fib[i] = fib[i - 1] + fib[i - 2];
	int N, M; cin >> N >> M;
	vec.emplace_back(0); vec.emplace_back(N + 1);
	for (int i = 0; i < M; i++) {
		int x; cin >> x;
		vec.emplace_back(x);
	}

	sort(vec.begin(), vec.end());

	int ans = 1;
	for (int i = 1; i <= M + 1; i++) {
		ans *= fib[vec[i] - vec[i - 1] - 1];
	}

	cout << ans;
}