BOJ2989 개구리 왕눈이

문제 링크 : BOJ2989

문제 요약

2차원 좌표에 점들이 있고 각 점에는 파리가 있다. 개구리는 처음에 힘이 0이고 파리를 먹어서 먹은 만큼 힘을 증가 시킬 수 있다. 1번점부터 시작하여 점에서 점으로 이동하여 N번째 점에 도착했을 때 힘이 최대가 되어야 한다. 점에서 점으로 이동 하려면 X좌표 또는 Y좌표가 같아야 하며 좌표가 증가해야 한다. 이동 할 때 마다 힘이 K만큼 감소하고 이동하는 도중에 힘이 음수가 되면 안된다.

위 이미지는 예제를 시각적으로 표현한 이미지이다. 왼쪽 하단의 노란색점이 1번점이고 오른쪽 상단의 노란색점이 N번째 점이다. 화살표는 점에서 점으로 갈 수 있는 방향을 의미하며 점에 쓰여있는 숫자는 파리의 양을 의미한다.
파리가 30만큼있는 점을 지나는 경로로 이동하면 최대일 것 같지만 힘이 부족하여 30만큼있는 점으로 이동 할 수 없다. 따라서 파리가 5만큼있는 점들을 지나서 이동하는게 최적이자 유일한 방법이고 N번째 점에 도달 했을 시 힘이 5가 된다.

문제 풀이

우선 점들을 좌표 기준으로 정렬하면 이동할 수 있는 경로는 사이클이 없는 구조임을 알 수 있다. (항상 좌표가 증가하는 방향으로 이동해야 하기 때문이다.)

DP[i] = 1번점부터 i번째 점까지 왔을 때 최대 힘

이라고 정의하면 간단한 \( O(N^2) \) 풀이를 떠올릴 수 있다. 하지만 N이 너무 커서 좀 더 효율적으로 계산 할 방법을 찾아야 한다. DP[i]를 계산할 때 다른 점들을 전부 볼 필요가 없다. X좌표가 같은 점들 중 DP[j]가 최대인 것과 Y좌표가 같은 점들 중 DP[j]가 최대인 것만 보면 된다. 이를 빠르게 알 수 있도록 보조로 xMX라는 배열을 만들어 xMX[x]에는 좌표가 x인 것 중에서 DP[j]값이 제일 큰 것을 저장하도록 한다. y좌표도 마찬가지로 처리 할 수 있다.
좌표를 기준으로 정렬 했으므로 처음과 순서가 다름에 유의하자.

소스코드 (Python3)

intINF = 10 ** 18
coordMX = 10 ** 5 + 1

if __name__ == "__main__":
    n, k = map(int, input().split())
    lotuses = []

    for i in range(n):
        lotuses.append(list(map(int, input().split())) + [i])

    lotuses.sort()

    xMX = [-intINF] * coordMX
    yMX = [-intINF] * coordMX
    xMXidx = [-1] * coordMX
    yMXidx = [-1] * coordMX
    dp = [-intINF] * n
    prv = [-1] * n
    destIdx = -1

    for i in range(n):
        x, y, flies, id = lotuses[i]

        if id == n-1: destIdx = i

        if id == 0: dp[i] = flies
        else:
            if xMX[x] >= k and xMX[x] - k + flies > dp[i]:
                dp[i] = xMX[x] - k + flies
                prv[i] = xMXidx[x]

            if yMX[y] >= k and yMX[y] - k + flies > dp[i]:
                dp[i] = yMX[y] - k + flies
                prv[i] = yMXidx[y]

        if xMX[x] < dp[i]: xMX[x], xMXidx[x] = dp[i], i
        if yMX[y] < dp[i]: yMX[y], yMXidx[y] = dp[i], i

    print(dp[destIdx])

    cur = destIdx
    path = []

    while cur != -1:
        path.append(cur)
        cur = prv[cur]

    path = path[::-1]

    print(len(path))
    for idx in path:
        print(lotuses[idx][0], lotuses[idx][1])