1981 배열에서 이동
-
백준 1981 배열에서 이동Algorithm/BOJ 2021. 4. 1. 21:05
출처: www.acmicpc.net/problem/1981 분류: 이분탐색 접근방식 이 문제는 n이 최대 100으로 100 x 100 배열이기 때문에 단순 무식하게 BFS 접근하면 시간초과를 맞게 됩니다. 어떻게 하면 방문을 범위를 제한할 수 있을까요? 이 문제에서도 이분탐색의 아이디어를 적용해볼 수 있습니다. 우선 차이가 가장 작아지는 경우는 언제일까요? 경로의 최대최소가 같은 경우면 차이가 최소가 될 수 있겠죠? 때문에 최소는 언제나 가능성이 있으니 0으로 둡니다. 그럼 차이가 최대가 될 때는 언제일까요? 배열에 나오는 최대값과 최소값이 모두 들어있을 때, 즉 최대 - 최소가 차이의 최대가 되겠네요. 저희는 최소를 구해야 하기 때문에 만약 0 ~ 8 까지 가능성이 있을 때, 차이를 4로해서 가는 경우..