[백준] 22871. 징검다리 건너기 (large)

백준 문제 풀이 - 이진탐색

📰 문제

문제 확인 🏃

💡 입출력 예제

5
1 4 1 3 1

>> 2

5
1 5 2 1 6

>> 6

💬 풀이

🎵 첫번째 풀이

참고. https://lietenant-k.tistory.com/10

import sys

input = sys.stdin.readline
N = int(input())                                # 돌의 개수
A = [0] + list(map(int, input().split()))       # 돌의 수 Ai

def solution(start, end):
    answer = 0

    while start <= end:
        mid = (start + end) // 2

        visited = [False] * (N+1)
        flag = False

        stack = [1]
        visited[1] = True

        while stack:
            now = stack.pop()

            if now == N:
                flag = True
                break

            for idx in range(now+1, N+1):
                temp = (idx - now) * (1 + abs(A[now] - A[idx]))
                if temp <= mid and not visited[idx]:
                    stack.append(idx)
                    visited[idx] = True

        if flag:
            answer = mid
            end = mid - 1
        else:
            start = mid + 1

    return answer

print(solution(1, (N-1) * (1 + abs(A[N] - A[1]))))

✒️ 생각

이진 탐색 코드를 변형해서 사용하는 건 처음.. stack과 함께 사용하다니
다른 분의 코드를 참고해서 문제를 풀었지만, 꼭 기억해놓고 다음엔 풀어야지