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

https://www.acmicpc.net/problem/22871

22871번: 징검다리 건너기 (large)

이분 탐색 카테고리 문제를 풀다가 접하게 된 문제다. 

연산시간 때문에 하루종일 이 문제만 붙잡고 고민했다. 최적화 하려는 변수가 M이라면 보통 이분탐색 문제는 O(log M) 시간안에 해결이 가능하거나 그 보다 오래 걸리더라도 주어진 시간 안에 해결이 가능했다. 관련하여 문제를 풀면서 고민한 것들을 글에 풀어서 써보겠다.

 

 N개의 징검다리가 있고 첫번째부터 출발해서 마지막 징검다리까지 가려고 한다. 두 다리 사이를 이동할 때 드는 힘(비용)을 고려해서 이동이 가능하다. 힘의 상한선을 정해두고 그 이하의 힘만을 써가면서 마지막 다리까지 도달해야 하는데, 그때 힘의 최솟값을 찾는 문제다.

 

이분 탐색으로 문제를 해결하기 위해 최적화 하려는 힘의 상한선을 x라고 둔다면 f(x)는 "x보다 작거나 같은 값만으로 첫번째 다리에서 마지막 다리까지 도달 하는지" 이다. 따라서 이 조건을 만족하는 x의 최솟값을 찾는다.

 

 힘의 상한선을 넘지 않고 마지막 다리까지 도달할 수 있는지 확인할 수 있는 방법은 무엇일까? 첫번째 다리에서 갈 수 있는 다리들을 모두 확인하고 그 다리로 이동하여 다시 그 다리에서 갈 수 있는 다리들을 확인한다. 갈 수 있는 다리라는 것은 다리를 건널때 필요한 힘이 상한선 이하라는 의미다. 결국 이런식으로 다리를 건넜을 때 마지막 다리에 도착할 수 있으면 마지막까지 도달하는 경우가 최소 1가지 존재한다는 뜻이므로 상한선을 낮춰서 같은 과정을 반복하고, 도달할 수 없다면 상한선을 높힌다.

 

 위 과정을 크게 2가지 방법으로 구현할 수 있고 소요되는 시간 복잡도는 동일하다.

1. DFS와 유사하게 스택을 사용하는 방법

2. 단순 이중 반복문을 사용하는 방법

 

(1) 스택을 사용한 DFS

과정을 자세히 보면 DFS와 유사하게 진행된다. 다리를 노드라고 보면 노드 사이에 힘이라는 비용이 존재한다. 뒤로는 이동할 수 없기 때문에 하나의 다리는 그 보다 번호가 큰 다리들이 연결돼있는 노드인 것이다. 노드를 방문하면서 방문한 노드와 연결된 모든 노드들의 비용을 확인하고, 조건에 맞으면 방문한다. 노드의 수는 최대 5000이므로 때문에 재귀로 구현하면 에러가 발생한다. 따라서 반복문을 이용한 스택으로 구현한다.

 

(2) 단순 이중 반복문 사용

참 또는 거짓값을 가지는 리스트를 다리 수 만큼 만든다. 1번 다리부터 N번 다리까지 확인하는데, 지금 확인하고 있는 다리가 참 값을 가지고, 그 다리보다 번호가 큰 다리들까지 가는 모든 힘을 계산해서 상한선보다 작거나 같은 힘으로 갈 수 있는 다리가 존재하면 그 다리(갈 수 있는 다리)에 참 값을 부여한다. 최종적으로 마지막 번호의 다리가 참값이면 도달할 수 있다는 의미이다. 값을 저장해놓고 사용한다는 측면에서 다이나믹 프로그래밍이라고 볼 수도 있겠다.

 

 위 두 방법은 결과적으로 모든 다리를 확인해서 그 다리보다 큰 번호의 다리들을 검사한다. 조건을 확인하는데 n(n+1)/2 만큼의 연산을 수행하고, 이분 탐색을 하는데 log M만큼 연산을 수행한다. 따라서 시간복잡도는 O((N*2)*log M) 이다. 이렇게 되면 총 연산횟수는 20억이 넘어가므로 PyPy로만 정답 판정을 받는다. 또한 1번 방법이 2번보다 훨씬 빠르다. 아래 소스코드는 1번으로 구현한 것이다.

 

이분 탐색이 아닌 다이나믹 프로그래밍으로도 해결이 가능하다. 이 경우는 O(N*2)시간으로 해결이 가능하므로 당연하게 위 방법보다 빠르다. (그런데 다이나믹 프로그래밍을 적용해도 PyPy 환경에서만 정답을 받을 수 있다.)

import sys
input = sys.stdin.readline

n = int(input())
stone = [0] + list(map(int, input().split()))
s, e, r = 1, (n-1) * (1 + abs(stone[n] - stone[1])), 0

while s <= e:
    m = (s + e) // 2
    flag = 0
    stack = [1]
    v = [False]*(n+1)
    v[1] = True
    
    while stack:
        k = stack.pop()

        if k == n:
            flag = 1
            break

        for i in range(k + 1, n + 1):
            p = (i - k) * (1 + abs(stone[i] - stone[k]))
            if p <= m and not v[i]:
                stack.append(i)
                v[i] = True

    if flag:
        e = m - 1
        r = m
    else:
        s = m + 1

print(r)