https://www.acmicpc.net/problem/2302
2302번: 극장 좌석
주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)
www.acmicpc.net
VIP 좌석 사이의 간격마다 경우의 수를 모두 구하고 곱하면 된다.
i번째 VIP 좌석과 i+1번째 좌석 사이의 간격을 d라 할 때
d = 0이면 경우의 수는 1
d = 1이면 경우의 수는 1
d = 2이면 경우의 수는 2
d > 2부터는 d - 1의 경우의 수와 d - 2의 경우의 수를 더하면 된다. (피보나치)
'알고리즘 > BOJ' 카테고리의 다른 글
| [BOJ 15480] LCA와 쿼리 (0) | 2020.04.24 |
|---|---|
| [BOJ 5214] 환승 (0) | 2020.04.21 |
| [BOJ 16639] 괄호 추가하기 3 (0) | 2020.03.14 |
| [BOJ 2263] 트리의 순회 (0) | 2020.03.11 |
