SCPC 6회 예선 [사다리 게임]
문제
위 Link 에서 "125번 SCPC 6회 예선 [사다리 게임]" 에 해당이 된다.
설명
- A 상태 : 아직 가로 이음선을 받기 전 상태
- B 상태 : 가로 이음선을 하나 받은 상태
- C 상태 : 가로 이음선을 2개 받은 상태
- D 상태 : 가로 이음선을 3개 받은 상태
- E 상태 : 가로 이음선을 4개 받은 상태
이렇게 해당이 된다. 저렇게 이음선을 하나하나 입력받을 때 마다 I --> J 로 가는 방법에서 고장난 가로 이음선의 최소개수를 계속해서 업데이트를 할 것이다.
dp[A][B] = A 에서 B 로 갈 때 고장난 가로 이음선의 최소개수
A 상태에는 I --> J ( I != J ) 에 해당이 되는 경로가 존재하지 않는다. 따라서 이 경우들은 모두 infinite 로 초기화를 하였고, I --> I 에 해당이 되는 경로는 모두 고장난 이음선이 존재하지 않고 바로 직행하여 갈 수 있으므로 0으로 초기화를 하였다.
B, C .. 상태에서는 가로 이음선이 생긴 두 사다리에 대한 값을을 업데이트 해야 한다.
위 사진의 B 상태는 직전에 1번 사다리와 2번 사다리를 이은 가로 이음선이 생긴 상태이다. 따라서, dp[k][1], dp[k][2] ( 1 <= k <= N ) 을 모두 업데이트를 해야 한다.
위 사진의 C 상태는 직전에 2번 사다리와 4번 사다리를 이은 가로 이음선이 생긴 상태이다. 따라서, dp[k][2], dp[k][4] ( 1 <= k <= N ) 을 모두 업데이트를 해야 한다.
...
위 사진의 E 상태는 직전에 1번 사다리와 4번 사다리를 이은 가로 이음선이 생긴 상태이다. 따라서 dp[k][1], dp[k][4] ( 1 <= k <= N ) 을 모두 업데이트를 해야 한다. 또한 여기서 구하는 dp 의 값들이 최종 dp 값이 된다.
업데이트 조건은 아래와 같다.
위 사진의 C 상태의 경우, 2번 사다리와 4번 사다리를 잇는 가로 이음선이 생김에 따라 이전까지 K ( 1 <= K <= N ) 번째 사다리에서 2번째 사다리를 온 경로는, 최종적으로 2----4 가로 이음선으로 인해 4번째 사다리로 오게 된다. 반대로 이전까지 K 번째 사다리에서 4번째 사다리를 온 경로는, 최종적으로 2---4 가로 이음선으로 인해 2번째 사다리로 오게 된다. 따라서 dp[k][2], dp[k][4] 의 값은 다음과 같이 업데이트를 할 수 있다.
dp[k][2] = min ( dp[k][2] + 1, dp[k][4] )
dp[k][4] = min ( dp[k][4] + 1, dp[k][2] )
dp[k][2] = min ( dp[k][2] + 1, dp[k][4] )
이전에 dp[k][2] 의 경로를 가지고 현재 dp[k][2] 에 오고싶으면, 지금 생긴 가로 이음선을 제거한 후 와야 하므로 dp[k][2] + 1 값에 해당이 되고, 이전에 dp[k][4] 의 경로를 가지고 현재 dp[k][2] 에 오고싶으면, 지금 생긴 가로 이음선을 타고 오게 되므로 dp[k][4]의 값에 해당이 된다.
dp[k][4] = min ( dp[k][4] + 1, dp[k][2] )
이전에 dp[k][4] 의 경로를 가지고 현재 dp[k][4] 에 오고싶으면, 지금 생긴 가로 이음선을 제거한 후 와야 하므로 dp[k][4] + 1 값에 해당이 되고, 이전에 dp[k][2] 의 경로를 가지고 현재 dp[k][4] 에 오고싶으면, 지금 생긴 가로 이음선을 타고 오게 되므로 dp[k][2]의 값에 해당이 된다.
이러한 방식으로 위 첨부된 예시 사다리 사진에서 A, B, ... , E 순서로 dp 의 값을 계속해서 업데이트 하면 된다. 그 후 입력되는 어떠한 사다리 (a) 에서 출발하여 어떠한 사다리(b) 로 가는 가로 이음선 고장의 최소값은 dp[a][b] 로 구하면 된다.
Code
|
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
|
#include <iostream>
#include <vector>
#define I first
#define J second
#define INF 1e9
using namespace std;
typedef pair<int, int> PII;
int Answer;
int main(int argc, char** argv)
{
int T, test_case;
int N, k, m;
cin >> T;
for (test_case = 0; test_case < T; test_case++)
{
cin >> N >> k >> m; // 사다리 개수, 가로선 개수,
vector<vector<int>> dp; // dp[A][B] == A 에서 B 로 갈 때 가로 이음선 제거 횟수의 최소값
dp.assign(N + 1, vector<int>(N + 1, INF)); // dp[A][B] == INF 의 경우, A 에서 B 로 가는 경로가 없는 경우이다.
for (int i = 1; i <= N; i++) dp[i][i] = 0; // dp[A][A] 는 초기 가로 이음선이 없는 경우 바로 직행하여 갈 수 있으므로
// 이 경우들은 모두 0으로 초기화를 한다.
PII row;
for (int i = 0; i < k; i++) {
cin >> row.I >> row.J; // row.I --- row.J 로 이어지는 가로 이음선 입력
int Itemp, Jtemp;
for (int s = 1; s <= N; s++) {
Itemp = dp[s][row.I];
Jtemp = dp[s][row.J];
dp[s][row.I] = min(Itemp + 1, Jtemp); // s 에서 row.I 로 가는 dp 의 최소값을 update
dp[s][row.J] = min(Jtemp + 1, Itemp); // s 에서 row.J 로 가는 dp 의 최대값을 update
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
int start, end; cin >> start >> end;
ans += (dp[start][end] != INF ? dp[start][end] : -1);
}
cout << "Case #" << test_case + 1 << endl;
cout << ans << endl;
}
return 0;
}
|
cs |
댓글