(BOJ 1800 인터넷 설치) 최적화 문제 → 결정문제, 이분법

처음에 MST, DFS, DP 풀이 생각함. 

• MST - MST 구한 뒤 간선 중 제일 비싼 거 K개 제외한 뒤 최댓값
  → MST는 모든 노드 연결하는데, 우리는 1과 N만 연결하면 돼서 X
• DFS - 모든 경우 탐색. 선택한 edge cost를 set 같은 곳에 저장한 뒤 (sorted), N 도달하면 ans update
  → 중복 탐색 많아서인지 TLE
• DP - dp(i) : i부터 N까지 K개 제외했을때 최댓값이 min이 되도록 선택한 cost들 (set<int>)
  →  만약 i부터 N까지 도달하는 경로 개수가 K개 이하라면, 무조건 최댓값이 0이라서 왜곡된 경로 선택 가능
  
• Shortest path (Dijkstra) : 다익스트라로 최단경로 찾은 뒤 제일 큰 K개 제외
  → 반례 존재 (그리디 방식 X)
  

  

  k=1일때 최단거리는 빨간색이지만, Dijkstra는 파란색 루트만 찾음 

  
  

각각 여러가지 문제점이 있었음.

 

정휘님 설명 보고 '최적화 문제' 임을 깨달음

https://justicehui.github.io/usaco/2019/07/12/BOJ1800/

백준1800 인터넷 설치

(배워야 할 점 : memset, 이분법 ans로 값 저장하고 mid-1, mid+1로 업데이트)

 

 

최적화 문제 → 결정문제로 바꿔서 이분법으로 푸는 방법을 사용.

모르면 종만북 Ch12를 꼭 참고하길 바람.

 

---

문제에서 조건주고 '최소의 값' 구하라고 함 = 최적화 문제 = mincost로 두고 이분법

 

결정 문제?
mincost 이하의 선들만 가지고 1과 N을 연결할 수 있나?
+ mincost 초과의 선들 K개까지 사용 가능 (→ 이 조건 어떻게 처리?)

(아이디어) mincost 이하의 edge는 0으로, 초과는 1로 두고 Dijkstra 돌림.
만약 최단거리가 K이하일 경우 ok, 초과인 경우 no

★ edge를 1로 두었기 때문에, 원래 cost가 뭐든지 상관없이 N으로의 최단거리 찾게 됨.
이때 K개 초과해서 사용하면 문제 조건 어기는 것.