[백준] 2302번: 극장 좌석 - 파이썬
2023. 1. 5. 20:36ㆍ백준 & 프로그래머스
문제보기
https://www.acmicpc.net/problem/2302
2302번: 극장 좌석
주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)
www.acmicpc.net
풀이 및 코드
해당 문제는 dp를 이용해 푸는 문제로, 필자는 vip석 사이의 좌석들에 대해 경우의 수를 구한 뒤 곱하는 방법으로 코드를 구현했다. 사용된 점화식은 다음과 같다.
# dp[i] => vip가 아닌 좌석이 연달아 i개 있을 때 경우의 수
dp[i] = dp[i-2] + dp[i-1]
필자는 모든 좌석이 vip좌석으로 되어 있을 때 0을 출력하도록 코드를 구현해 여기서 삽질을 좀 했다..
'백준 & 프로그래머스' 카테고리의 다른 글
| [백준] 1949번: 우수 마을 - 파이썬 (0) | 2023.01.07 |
|---|---|
| [백준] 1520번: 내리막 길 - 파이썬 (0) | 2023.01.05 |
| [백준] 16236번: 아기 상어 - 파이썬 (2) | 2023.01.04 |
| [백준] 16235번: 나무 재테크 - python (0) | 2023.01.02 |
| [백준] 15685번: 드래곤 커브 (0) | 2022.12.27 |