문제) 백준 - 동적 계획법 - 극장 좌석
https://www.acmicpc.net/problem/2302
2302번: 극장 좌석
주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)
www.acmicpc.net
VIP 좌석을 제외한 연속된 i개 자리에 대하여 피보나치 수열 i개로 사람들을 앉힐 수 있습니다. 동적 계획법을 통해 피보나치 수를 구하고 입력으로 들어온 VIP 좌석마다 ans에 곱합니다.
C++ 소스코드)
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
| [백준] 3584번 - 가장 가까운 공통 조상 (C++) 문제 및 풀이 (0) | 2022.02.19 |
|---|---|
| [백준] 6118번 - 숨바꼭질 (C++) 문제 및 풀이 (0) | 2022.02.19 |
| [백준] 21919번 - 소수 최소 공배수 (C++) 문제 및 풀이 (0) | 2022.02.18 |
| [백준] 21610번 - 마법사 상어와 비바라기 (C++) 문제 및 풀이 (0) | 2022.02.17 |
| [백준] 14712번 - 넴모넴모 (Easy) (C++) 문제 및 풀이 (0) | 2022.02.17 |
댓글