1516 Developing game
알고리즘(위상정렬, 그래프. DP)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1. 어떤 건물을 짓기 위해 필요한 건물을 짓는 시간의 최대 + 이 건물을 짓는데 걸리는 시간을 출력하면 됨.
2. 예를 들어
A -> -> D
C
B -> -> E
로 그래프가 이루어져 있을 때,
A : A를 짓는 시간
B : B를 짓는 시간
C : max(A, B) + C를 짓는데 걸리는 시간
D : C + D를 짓는데 걸리는 시간
E : C + E를 짓는데 걸리는 시간
이기 때문이다.
물론 모든 건물은 지어질 수 있는 상태일 때 바로 짓는 것을 가정한다.
3. 나는 이걸 무한루프로 모든 건물을 검사할 때까지, 모든 건물을 처음부터 끝까지 확인하는 식으로 구현하였다.
최대 건물의 수가 500개이니 선형일경우 최악 25000이기에 충분히 시간이 많다고 생각했기 때문이다.
하지만, 더 빠른 방법은 위상정렬을 하여 하는 방법이다.
그래프가 그려져 있는 대로 정렬을 하여야한다.
예를 들어, 위의 예에선 A B C D E 순으로 정렬이 되어야한다.
이렇게하면, 무한루프로 할 필요없이 처음부터 그냥 쑥훑으면서 검사하면 끝나기 때문이다.
기타
1
2
1. 위상정렬 하는 법 알아보기 -> 알아봤는데 굳이 위상정렬 배열을 만들 필요는 없는 거 같다.
2. DP : 왜 알고리즘 분류에 DP가 들어갔나 했더만, 이미 검사한 거는 check표시하여 검사하지않고, 최댓값을 다음 노드로 계속 넘겨주는 형태가 DP인거 같다.
코드
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
#include <bits/stdc++.h>
#define MAX_LENGTH 100
#define DIV 1000000000
#define ALL 1023
using namespace std;
int N, num[101];
long long DP[101][10][1 << 10];
long long getAnswer(int, int);
int main() {
cin >> N;
memset(DP, -1, sizeof(DP));
long long result = 0;
for (int i = 1; i <= 9; i++) {
num[0] = i;
result += getAnswer(1, 1 << i);
}
cout << result % DIV << endl;
}
long long getAnswer(int deep, int bit) {
if (deep == N) {
if (bit == ALL)
return 1;
return 0;
}
if (DP[deep][num[deep - 1]][bit] != -1)
return DP[deep][num[deep - 1]][bit];
long long result = 0;
if (num[deep - 1] != 0) {
num[deep] = num[deep - 1] - 1;
int b = bit & (1 << num[deep]) ? bit : bit + (1 << num[deep]);
result += getAnswer(deep + 1, b);
}
if (num[deep - 1] != 9) {
num[deep] = num[deep - 1] + 1;
int b = bit & (1 << num[deep]) ? bit : bit + (1 << num[deep]);
result += getAnswer(deep + 1, b);
}
return DP[deep][num[deep-1]][bit] = result % DIV;
}