📝 문제 정보#
🧐 관찰 및 접근#
- 생각하기 쉽게, $N$번 주제인 “그팩주” 근처에서 생각해보자.
- 어떤 정점에서, 다음 정점 중 $N$번 정점이 있다면 준표는 화제를 그 정점으로 보내면 안된다.
- 만영이의 차례에서 만영이는 다음 간선중 최대한 기댓값이 높은 정점으로 가려고 한다.
- 그것들을 하나하나 반려해가는 맛인데..
- DP식을 이런식으로 세울 수 있을까?
- $\text{DP}[i][a]$ : $i$번 정점에서 $a$번사람의 턴일때 기댓값
- $\text{DP}[i][jun] = \min\limits_{nxt: links[i]}(\text{DP}[nxt][man])$
- $\text{DP}[i][man] = \min\limits_{nxt: links[i]}(\text{DP}[nxt][jun] + cnt)$
- 예를들어 만영이가 고르 수 있는 다음 정점이 $N, i, j, k$라고 하고, 기댓값은 각각 $1e9, 10, 10, 9$라고 하자.
- $N$은 고르면 안되므로, 무조건 반려한다. 그러면 만영이는 10을 고르고, 이때 기댓값은 11이다.
- 마지막 9를 고르기 위해 3번 반려해버리면 오히려 기댓값이 12이므로, 그러면 안된다! 따라서 내림차순으로 정렬한뒤 인덱스를 더해서 정리해보자.
- $\text{DP}[i][a]$ : $i$번 정점에서 $a$번사람의 턴일때 기댓값
- ![[Drawing 2026-02-12 10.30.22.excalidraw.png]]
- 예제 3번의 그림
💻 풀이#
- 코드 (C++):
int calc(int cur, int turn){
if(DP[cur][turn] != -1) return DP[cur][turn];
int &ret = DP[cur][turn];
ret = 1e9;
if(turn == 0){ // 준표의 턴
for(auto nxt: links[cur]) ret = min(ret, calc(nxt, 1));
return ret;
}
else{ // 만영이의 턴
vector<int> v;
for(auto nxt: links[cur]) v.push_back(calc(nxt, 0));
sort(all(v), greater<int>());
rep(i, 0, v.size()) ret = min(ret, v[i] + i);
return ret;
}
}
void solve(){
cin >> N >> E;
rep(i, 0, E){
int u, v; cin >> u >> v;
links[u].push_back(v);
inDeg[v]++;
}
rep(i, 0, N+1) DP[i][0] = DP[i][1] = -1;
DP[N][0] = 1e9;
DP[N][1] = 0;
int ans = 1e9;
rep(i, 1, N+1) if(inDeg[i] == 0) ans = min(ans, calc(i, 1));
if(ans == 1e9) cout << -1 << '\n';
else cout << ans << '\n';
}