728x90
SMALL
백준 문제 풀이: 2302 [극장 좌석]
문제 링크: https://www.acmicpc.net/problem/2302
문제 설명:
극장 좌석이 한 줄로 배치되어 있고, 특정 좌석은 VIP로 고정되어 있어 자리를 바꿀 수 없습니다. 나머지 좌석은 자유롭게 배치할 수 있으며, 극장 좌석의 배치 방법의 가짓수를 계산하는 문제입니다.
- VIP 좌석은 고정되어 이동할 수 없습니다.
- 인접한 두 좌석을 서로 바꾸는 방식으로 자유 좌석의 배치를 다양하게 구성할 수 있습니다.
문제 해결 코드
#include <iostream>
using namespace std;
int dp[41]; // DP 배열: 각 구간의 좌석 배치 방법의 가짓수를 저장
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n; // 좌석의 총 개수
cin >> n;
int m; // VIP 좌석의 개수
cin >> m;
if (n == m) { // 모든 좌석이 VIP라면 배치 방법은 1가지
cout << 1 << '\n';
return 0;
}
// DP 초기값 설정
dp[0] = 1; // 좌석이 없는 경우 1가지 배치 가능 (빈 경우)
dp[1] = 1; // 좌석이 1개인 경우 1가지 배치 가능
dp[2] = 2; // 좌석이 2개인 경우 (교환 가능)
// DP 계산: 피보나치 점화식 적용
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int ans = 1; // 전체 배치 방법의 가짓수
int prevVip = 0; // 이전 VIP 좌석의 위치
// VIP 좌석 정보를 기반으로 계산
for (int i = 0; i < m; i++) {
int vip;
cin >> vip;
ans *= dp[vip - 1 - prevVip]; // VIP 구간 이전의 배치 방법 곱하기
prevVip = vip;
}
// 마지막 구간 배치 방법 추가
ans *= dp[n - prevVip];
// 결과 출력
cout << ans << '\n';
return 0;
}
코드 설명
- 핵심 알고리즘: 자유 좌석 구간을 나누어 각각의 배치 방법을 계산하고 이를 곱합니다. 각 구간의 배치 방법은 피보나치 수열을 이용해 계산합니다.
- 구현 세부사항:
dp[i]
: 좌석이i
개일 때의 배치 방법의 가짓수- VIP 좌석으로 인해 나뉘는 자유 구간의 길이를 계산하고, 해당 구간의 배치 방법을 곱합니다.
- 마지막 자유 구간에 대해 추가로 계산합니다.
- 시간 복잡도 분석: O(n)
- DP 배열 계산: O(n)
- VIP 좌석 처리: O(m), 여기서 m은 VIP 좌석의 개수
결과
좌석 배치 방법의 총 가짓수를 정확히 계산합니다. VIP 좌석에 의해 구간이 나뉘는 문제를 피보나치 수열을 활용하여 효율적으로 해결했습니다.
다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!
728x90
LIST
'BAEKJOON > 다이나믹 프로그래밍' 카테고리의 다른 글
백준 9465번 [스티커](C++) -yes6686- 티스토리 (1) | 2024.01.31 |
---|---|
백준 11052번 [카드 구매하기](C++) -yes6686- 티스토리 (1) | 2024.01.30 |
백준 15988번 [1, 2, 3 더하기 3](C++) -yes6686- 티스토리 (1) | 2024.01.28 |
백준 2579번 [계단 오르기] (C++) -yes6686- 티스토리 (1) | 2024.01.28 |
백준 2156번 [포도주 시식] (C++) -yes6686- 티스토리 (0) | 2024.01.28 |