백준2302

[백준 2302] 극장 좌석 C++

www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석의 문제는 다이나믹 프로그래밍 문제로, 수열의 규칙을 찾아보면, 피보나치 수열임을 알 수 있습니다. 그 원리를 이용해서 해당 구간의 경우의 수를 곱해주는 문제입니다. 문제에서 VIP좌석이 있지만, 일단 우리는 VIP좌석을 빼고 규칙성을 찾아봅시다. VIP좌석을 빼고 규칙을 찾으면 1부터 N까지의 가능한 경우의 수는 1번째 = 1 2번째 = 2 3번째 = 3 4번째 = 5 5번째 = 8 6번째 = 13 7번째 = 2..