백준 14948 - 군대 탈출하기 (C++)

문제 문제 링크 BOJ 14948 - 군대 탈출하기 문제 요약 $N*M$의 맵이 주어지고 $(1, 1)$에서 $(N, M)$으로 이동하려 한다. 최소 각 칸에 적힌 레벨만큼은 되어야 해당 칸을 지날 수 있고 딱 한 번 한 칸을 건너뛸 수 있을 때, 갖춰야 하는 최소 레벨을 구해보자.

제한 TL : $1$ sec, ML : $256$ MB $1 ≤ n, m ≤ 100$ $0 ≤ k ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 이분 탐색(binary search) 매개 변수 탐색(parametric search) 풀이 문제 내용과 $k$의 범위만 봐도 파라매트릭 냄새가 솔솔 난다. 다음과 같이 결정 문제를 정의해보자.

$f(x)$.....