728x90
문제
어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.
그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.
예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.
2. 코드
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
# vip 좌석을 true 체크 하기 위한 리스트
check = [False] * (n + 1)
# vip 좌석 true
for i in range(m):
check[int(input())] = True
# 경우의 수 계산을위한 리스트
dp = [0] * 41
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
cnt = 0
ans = 1
# 1 ~ n 까지 vip 좌석이 아닌 것중 연속됨을 체크
for i in range(1, n + 1):
if not check[i]:
cnt += 1
else:
# vip를 만나고 cnt 가 0이 아니라면 경우의 수 곱
ans *= dp[cnt]
cnt = 0
# 처리 못한 cnt 체크 와 동시에 경우의수 곱하기
ans *= dp[cnt]
print(ans)
3. 회고
Q. 문제 해결 법
- 1. vip가 없을때 경우의수 구하는 식을 규칙성을 통해 구한다. ex) 좌석이 한개 일떄 경우의수 1, 좌석이 두개 일떄 경우의수 2, 좌석이 세개 일떄 경우의수 3 => dp[n] = dp[n - 1] + dp[n - 2] 이 규칙이 만들어 진다.
- vip 좌석을 만나기전에 일반좌석의 개수를 카운트
- 일반 좌석 카운트 한 값을 dp[cnt] 에 적용하여 정답에 곱 한다.
4. 고쳐야 할점
규칙성을 찾는 다이나믹 프로그래밍을 많이 연습해야될것같다.
728x90
'Algorithm > Python' 카테고리의 다른 글
백준 23061번 백남이의 여행 준비 (0) | 2023.02.09 |
---|---|
백준 7569번 토마토 (0) | 2023.02.05 |
백준 12834번 주간 미팅 (0) | 2023.02.01 |
백준 1202번 보석도둑 (0) | 2023.02.01 |
프로그래머스 부대복귀 (0) | 2023.01.29 |