반응형
https://www.acmicpc.net/problem/2302
2302번: 극장 좌석
주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)
www.acmicpc.net
[ 문제풀이 ]
1. dp [ i ] 주변에 vip 좌석이 없을 때 i명의 사람들이 앉을 수 있는 경우의 수입니다.
2. dp[dp [ i ] = dp [ i - 1 ] + dp [ i - 2 ]의 점화식을 이용하여 dp배열을 채웁니다.
3. ans = 1을 대입하고, vip의 위치가 입력될 때마다 그 사이의 사람 수를 dp배열에 넣어서 ans에 곱해줍니다.
4. ans를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include<iostream> using namespace std; int N, M; int dp[41]; int ans = 1; int main() { scanf("%d %d", &N, &M); dp[0] = 1; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= N; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } int before = 0; if (M == 0) { printf("%d", dp[N]); return 0; } for (int i = 0; i < M; i++) { int num; scanf("%d", &num); ans *= dp[num - before - 1]; before = num; } ans *= dp[N - before]; printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2157번 - 여행 (C++) (0) | 2022.11.02 |
|---|---|
| [ 백준 ] 2666번 - 벽장문의 이동 (C++) (0) | 2022.11.01 |
| [ 백준 ] 1309번 - 동물원 (C++) (0) | 2022.10.30 |
| [ 백준 ] 1965번 - 상자넣기 (C++) (0) | 2022.10.29 |
| [ 백준 ] 1890번 - 점프 (C++) (0) | 2022.10.28 |