백준 16117 - 실버런 (Python)

문제 정보

• https://www.acmicpc.net/problem/16117
• DP, 많은 조건 분기

---

문제 정리

N행 M열의 격자에 실버 주머니들이 놓여 있다. 이 실버 주머니들은 매초 왼쪽으로 한 칸씩 이동한다. 플레이어는 시작점을 임의로 잡을 수 있으며(정수 좌표가 아니어도 됨), 이후 매초 위/아래/오른쪽으로 1칸씩 이동할 수 있다. 단, 제자리에 멈출 수는 없으며, 1초 단위로만 움직일 수 있다. 이 때, 얻을 수 있는 실버의 최대 합을 구하는 문제이다.

---

풀이

처음 문제를 봤을 때 살짝 변형된 RGB 거리 문제같아서 일단 DP 코드를 작성했다. 그런데 예제2의 정답이 아무리 봐도 이해가 되지 않았고, 에디토리얼을 확인해보니 다음과 같은 이동으로 469를 만들 수 있었다.

• (2.5, 0.5) -> 95 획득 -> (3.5, 1.5) -> 97 획득 -> (4.5, 2.5) -> 96 획득 -> (3.5, 3.5) -> 98 획득 -> (2.5, 4.5) -> 71 획득 -> (3.5, 5.5).

시작점이 정수 좌표가 아니어도 된다는 말이 괜히 있는게 아니었다.
그래서 (정수 좌표에서 시작하는 DP) + (.5 좌표에서 시작하는 DP) 두 경우로 나누어 각각 DP를 계산하면 되겠다고 생각을 했다.

근데 함정이 하나 더 있었다.
정수 좌표에서 시작하는 경우, (x, y)에서 1초 후 도착할 수 있는 위치는 다음 세 종류인데,

• (x, y) -> (x+1, y+1)
• (x, y) -> (x-1, y+1)
• (x, y) -> (x, y+2)

여기서 아래 반례를 보자.

2 6
0 102 103 104 0 0
101 0 0 0 105 106

위 규칙만 그대로 적용하면
101 -> 102 -> 103 -> 104 -> 105 -> 0대로 이동하여 515가 최대값이라고 생각할 수 있다.

그런데 105 위치에서 앞으로 이동할 경우, 106을 획득하고 한칸 앞으로 가게 된다.
이런 경우를 처리하기 위해 끝 점의 한 칸 전(y=M-1)위치에서 앞으로 이동하는 경우를 따로 처리해줘야 한다.
같은 원리로, 시작 직후에도 예외가 생긴다.
즉, y=-1에서 앞으로 이동하여 y=1에 도착하는 경우도 따로 처리해 줘야 한다.

---

후기

엣지케이스 때문에 4WA. 생각보다 많이 어렵네 하고 보니까 G1이었다.

---

코드

# 백준 16117

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def solve(X, Y, silver):
    # 정수 좌표 시작 DP
    DP = [[0] * X for _ in range(Y)]
    for x in range(X):
        DP[0][x] = silver[0][x]
    for y in range(1, Y):
        for x in range(X):
            if x > 0:       # 위로 이동
                DP[y][x] = max(DP[y][x], DP[y-1][x-1] + silver[y][x])
            if x < X-1:     # 아래로 이동
                DP[y][x] = max(DP[y][x], DP[y-1][x+1] + silver[y][x])
            if y > 1:       # 앞으로 이동
                DP[y][x] = max(DP[y][x], DP[y-2][x] + silver[y-1][x] + silver[y][x])
            if y == 1:      # -1에서 앞으로 이동
                DP[y][x] = max(DP[y][x], DP[y-1][x] + silver[y][x])
            if y == Y-1:    # Y-1에서 앞으로 이동
                DP[y][x] = max(DP[y][x], DP[y-1][x] + silver[y][x])

    result = max(DP[Y-1])

    # .5 좌표 시작 DP
    DP = [[0] * (X+1) for _ in range(Y+1)]
    for y in range(1, Y+1):
        DP[y][0] = DP[y-1][1] + silver[y-1][0]
        DP[y][X] = DP[y-1][X-1] + silver[y-1][X-1]
        for x in range(1, X):
            DP[y][x] = max(DP[y-1][x-1] + silver[y-1][x-1], DP[y-1][x+1] + silver[y-1][x])

    result = max(result, max(DP[Y]))
    return result


def main():
    X, Y = map(int, input().split())
    silver = [[0] * X for _ in range(Y)]
    for x in range(X):
        for y, v in enumerate(list(map(int, input().split()))):
            silver[y][x] = v

    print(solve(X, Y, silver))


main()