문제 링크 : https://www.acmicpc.net/problem/2302
문제 풀이
이 문제에서는 좌석들의 정보(VIP여부)가 주어졌을 때 가능한 모든 좌석 배치의 경우의 수를 묻는 문제이다.
당연히 VIP 좌석 때문에 나눠진 좌석들끼리는 서로 영향을 주지 못하기 때문에 각각의 경우의 수를 구하고 곱해야겠다는 생각을 했다. 또 이 가능한 경우의 수는 DP를 이용하면 쉽게 구할 수 있었다. n명의 사람이 있고, VIP가 없을 때 가능한 좌석 배치를 D[n]이라고 하면, 처음 1과 2가 자리를 바꿀 때 나머지 남은 사람이 n-2명이므로, D[n-2]이고, 처음 1과 2가 자리를 바꾸지 않을 때는 1을 제외하면 n-1명이므로 D[n-1]이다.
D[n] = D[n-1] + D[n-2] (n>2)
2 (n=2)
1 (n=1)
따라서 다음과 같은 아주 간단한 점화식을 얻을 수 있다. 이제 이 점화식을 이용하면 쉽게 구할 수 있다. 문제에 나온 예시로 설명을 하면,
1~3좌석 까지는 D[3]의 경우의 수, 5~6까지는 D[2], 8~9까지도 D[2]의 경우의 수를 가지므로 답은 D[3] x D[2] x D[2] = 12가 된다.
시행착오
예제로 컴파일 해봤을 때 잘 나와서 바로 채점해봤더니 틀렸다고 나와서 무척 당황했다. 근데 저번에 볼 모으기 때 했던 실수 덕분에 어디서 잘못되었는지 바로 찾을 수 있었다. 원래 코드에서는 D[0]를 그냥 0으로 두었는데,
for(int i=1; i<=N+1; i++)
{
if(!SVIP[i])
{
k++;
}
else
{
nc *= D[k];
k = 0;
}
}
그렇게 되면 이 부분에서 만약 VIP좌석이 연속해 있을 때 전체 경우의 수 nc에 D[0]=0 이 곱해져서 값이 잘못 나오게 되었다. 그래서 D[0]을 1로 설정했어야한다.
코드
#include <iostream>
using namespace std;
int main() {
int D[41]={0,},N,M,VIP,nc=1,k=0;
bool SVIP[42] = {false,};
cin>>N;
D[0] = 1;
D[1] = 1;
for(int i=2; i<=N; i++)
{
D[i] = D[i-1] + D[i-2];
}
cin>>M;
while(M--)
{
cin>>VIP;
SVIP[VIP] = true;
}
SVIP[N+1] = true;
for(int i=1; i<=N+1; i++)
{
if(!SVIP[i])
{
k++;
}
else
{
nc *= D[k];
k = 0;
}
}
cout<<nc;
}
'정보 > 백준 문제풀이' 카테고리의 다른 글
백준 1713번 후보 추천하기 C++ (1) | 2024.01.06 |
---|---|
백준 2628번 종이자르기 C++ (1) | 2023.12.23 |
백준 17615번 볼 모으기 C++ (1) | 2023.12.17 |
백준 10799번 쇠막대기 C++ (1) | 2023.12.16 |
백준 1244번 스위치 켜고 끄기 C++ (1) | 2023.12.16 |