백준 22871번 : 징검다리(large)

https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이분 탐색 카테고리 문제를 풀다가 접하게 된 문제다. 연산시간 때문에 하루종일 이 문제만 붙잡고 고민했다. 최적화 하려는 변수가 M이라면 보통 이분탐색 문제는 O(log M) 시간안에 해결이 가능하거나 그 보다 오래 걸리더라도 주어진 시간 안에 해결이 가능했다. 관련하여 문제를 풀면서 고민한 것들을 글에 풀어서 써보겠다. N개의 징검다리..