반응형
극장 좌석
-
BOJ) 극장 좌석알고리즘/백준 2021. 2. 12. 15:52
극장 좌석 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 1 ~ N 까지 극장에 좌석이 존재한다. VIP 티켓을 가진 사람은 티켓에 적힌 번호에 딱 앉는다. 나머지 일반 티켓의 경우 좌우로 1씩 증감한 번호에 앉을 수 있다. 이 때, 좌석에 배치할 수 있는 좌석표의 경우의 수를 구하는 문제다. 문제 자체는 크게 어렵지 않았다. N =1 일 때, 1가지 경우가 존재하고, N =2 일 때, 2가지 경우 (1, 2) 와 (2,1)이 존재한다. N =3 일 때, (1,2,3), (1,3,2), (2,1,3)이 존재한다. 같은 ..