문제
풀이
처음에 dp인지 완전탐색인지 헷갈렸던 문제
최대 21억 개의 가짓 수가 있는 것 보고 dp일거 같았다.
자신의 번호와 다른 자리에 앉을 때는, 항상 그 사람과 나의 자리를 바꿔서 앉는다는 것에 초점을 두고 고민했다.
1, 2, 3 세 명을 자리에 앉힌다고 가정하자.
1과 2, 2와 3을 서로 바꿔 앉게 할 수 있다.
1, 2를 먼저 앉힐 때
1 2 또는 2 1이 가능하다.
이 때 3을 앉힐 때
1 2 뒤에 3을 앉혀 1 2 3을 만들거나 1 3 2로 바꿔 앉을 수 있고
2 1 뒤에 3을 앉혀 2 1 3을 만들 수 있다.
따라서 경우의 수는 3가지다.
이를 일반화시키면 다음과 같다.
마지막 번호를 N이라고 하고 번호 n까지의 앉는 경우의 수를 result[n]이라고 하자.
1. 마지막 번호가 VIP거나 마지막 번호의 앞 번호가 VIP인 경우
마지막 사람이 자리를 바꿀 수 없으므로 그대로 앉아야 한다. 마지막 번호 전 N-1 까지의 경우의 수가 그대로 유지된다.
따라서 result[N] = result[N - 1]이다.
마지막 번호와 마지막 번호의 앞 번호 모두 VIP가 아니라면 자리를 바꿀 수 있다.
2-1. 자리를 바꾸지 않고 마지막 번호가 마지막 자리에 앉는 경우
마지막 번호를 끝에 앉히면 되므로 그 전 번호까지 경우의 수가 그대로 유지된다.
즉, result[N - 1]개의 경우의 수가 존재한다.
2-2. 마지막 사람이 그 앞 사람과 자리를 바꾸는 경우
그 앞앞사람 (3인경우 1) 까지의 경우의 수 + 마지막 사람과 그 전 사람이 자리 바꿔 앉기의 경우의 수가 가능하다.
따라서 그 전전 번호까지 경우의 수가 그대로 유지된다.
즉, result[N - 2]개의 경우의 수가 존재한다.
따라서 result[N] = result[N - 1] + result[N - 2]이다.
소스 코드
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 main()
{
bool isVIP[41] = {};
int result[41] = {};
int N = 0;
int M = 0;
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int idx = 0;
cin >> idx;
isVIP[idx] = true;
}
result[1] = 1;
if (isVIP[1] || isVIP[2])
result[2] = 1;
else
result[2] = 2;
for (int idx = 3; idx <= N; idx++)
{
if (isVIP[idx - 1] || isVIP[idx])
result[idx] = result[idx - 1];
else
result[idx] = result[idx - 2] + result[idx - 1];
}
cout << result[N];
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
[백준 2564] 경비원 C++ (3) | 2023.05.30 |
---|---|
[백준 4811] 알약 C++ (0) | 2023.05.15 |
[백준 5972] 택배 배송 C++ (1) | 2023.03.03 |
[백준 10025] 게으른 백곰 C++ (0) | 2023.02.23 |
[백준 2473] 세 용액 C++ (10) | 2023.02.20 |