💡 다이나믹 프로그래밍
Memory 2020KB Time 0ms Code Length 1243B
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
using namespace std;
int N, M;
int fixed_sit[41];
int dp[41];
//int visited[41];
void init() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
int num;
cin >> num;
num--;
fixed_sit[num] = 1;
//visited[num] = 1;
}
}
unsigned int result = 0;
//void dfs(int depth) {
// if (fixed_sit[depth] == 1) { // 고정석이면 다음 인덱스로 넘어감
// dfs(depth + 1);
// return;
// }
// if (depth == N) {
// result++;
// return;
// }
// for (int i = -1; i <= 1; i++) {
// int next_idx = depth + i;
// if (next_idx < 0 || next_idx >= N) continue;
// if (visited[next_idx] == 1) continue;
// visited[next_idx] = 1; // 방문처리
// dfs(depth + 1);
// visited[next_idx] = 0; // 방문 취소
// }
// return;
//}
void make_dp() {
// 현재꺼는 전에꺼 더하기 전전에꺼
// 고정 좌석이라면 전에꺼 더하기
// 전의 인덱스가 고정 좌석이라면 전에꺼 더하기
dp[0] = 1;
if (fixed_sit[0] == 1 || fixed_sit[1] == 1) dp[1] = 1;
else dp[1] = 2;
for (int i = 2; i < N; i++) {
if (fixed_sit[i - 1] == 1 || fixed_sit[i] == 1) dp[i] = dp[i - 1];
else dp[i] = dp[i - 2] + dp[i - 1];
}
result = dp[N - 1];
}
int main() {
init();
//dfs(0);
make_dp();
cout << result;
}
이 코드는 좌석이 일렬로 배치된 극장에서 일부 좌석이 이미 고정되어 있을 때, 남은 좌석에 대한 경우의 수를 구하는 프로그램이다.
init 함수에서는 전체 좌석 수(N)와 이미 고정된 좌석의 수(M)을 입력받고, 고정된 좌석을 배열에 표시한다.
make_dp 함수에서는 동적 계획법을 사용하여 각 좌석마다의 경우의 수를 계산한다. 이때, 현재 좌석이 고정되어 있거나 바로 이전 좌석이 고정되어 있으면 경우의 수는 이전 좌석과 동일하다. 그렇지 않은 경우에는 이전 좌석과 전전 좌석의 경우의 수를 더한 값이 된다.
main 함수에서는 init 함수를 통해 입력을 받고, make_dp 함수를 호출하여 경우의 수를 계산한 뒤 결과를 출력한다.
