2253 : 점프 Python

2253 : 점프

처음에는 갈 수 있는 가지수인줄 알았는데 최소 움직임 횟수였다.

명심할 것

• 문제 잘 꼼꼼히 읽기
• 경계값 체크하기기존 코드에서는 2번째 칸을 무조건 이동가능하게 해뒀는데 2번째 칸 역시 작아서 밟지 못할 수 있다.
• 이 부분에서 문제가 생겨서 계속 오류가 났다.

예제와 같이 6, 11, 16번 칸을 못 밟는 경우 아래와 같다.

1번째 칸에서 한칸만 이동 가능하다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
1	0	1
2
3
4
5
6
7

2번째 칸에서는 1의 속도로 점프했으므로 다시 1의 속도로 점프하거나, 가속해서 2의 속도로 점프할 수 있다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
1	0	1	2
2				2
3
4
5
6
7

따라서, 현재 3번 칸과 4번 칸으로 이동할 수 있는 최소 점프 수는 2이다.

이제 3번째 칸을 살펴보자.

3번째 칸에서도 역시 1의 속도와 2의 속도로 점프할 수 있다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
1	0	1	2	3
2				2	3
3
4
5
6
7

4번째 칸에서는 1의 속도로 이동한 상태와 2의 속도로 이동한 상태가 모두 존재한다.

1의 속도로 이동한 상태에서 다시 1의 속도와 가속한 2의 속도로 이동할 수 있다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
1	0	1	2	3	4
2				2	3
3
4
5
6
7

먼저 1의 속도로 이동한 상태에서 1의 속도로 이동하면 5로 이동하는 최소 점프수는 4이다.

그러나 2의 속도로 5로 이동하는 경우 기존의 최소 점프와 현재 상태의 점프 횟수 + 1을 비교해 더 낮은 점프 수가 들어가게 된다.

따라서, 1의 속도로 이동한 상태(3회) + 다시 2의 속도로 이동(1)과 기존의 2의 속도로 5번째 칸으로 이동하는 최소 점프 횟수(3)을 비교해야 한다. 최솟값은 기존의 점프 횟수인 3이므로 변경되지 않는다.

이제 4번째 칸까지 2의 속도로 이동한 상태를 보자.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
1	0	1	2	3	4
2				2	3
3
4
5
6
7

2의 속도로 이동한 상태에서는 감속한 1의 속도와 그대로 2의 속도, 가속한 3의 속도로 이동할 수 있다.

2의 속도로 이동한 상태의 최솟값(2) + 1의 속도로 점프(1)과 기존 5번째 칸으로 1의 속도로 이동한 최소 점프 수(4)의 최솟값은 3이므로 5번째 돌로 1의 속도로 점프한 최솟값은 3으로 갱신된다.

2의 속도 그대로 점프했을 때는 6번째 돌에 닿는데 이는 너무 작아서 이동할 수 없기 때문에 갱신되지 않고, 3의 속도로 점프했을 때만 2 + 1 = 3으로 갱신된다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
1	0	1	2	3	3
2				2	3
3							3
4
5
6
7

이제 감이 좀 잡혔을 것 같다. 중요한 정보는 속도와 현재 칸이다. 따라서, DP 배열에 속도와 현재 칸에 대한 정보를 저장하면 dp[a][b] = c, a의 속도로 b칸으로 이동하는 최소 움직임 수는 c이다.

최솟값 갱신은 감속, 그대로, 가속 3가지 경우 중 하나다.

1. 속도 감속을 할 경우
2. dp[현재 속도 - 1][현재 칸 + (현재 속도 -1)] = 기존에 계산했던 최소 움직임과 dp[현재 속도][현재 칸] + 1 중 더 작은 값
3. 속도 그대로 이동할 경우
4. dp[현재 속도][현재 칸 + 현재 속도] = 기존에 계산했던 최소 움직임과 dp[현재 속도][현재 칸] + 1 중 더 작은 값
5. 속도 가속을 할 경우
6. dp[현재 속도 + 1][현재 칸 + (현재 속도 + 1)] = 기존에 계산했던 최소 움직임과 dp[현재 속도][현재 칸] + 1 중 더 작은 값

N이 최대 10,000칸이므로 속력을 계속 증가 시켰을 때 최대 141의 속도까지 낼 수 있다. 따라서 최대 속도는 141로 잡고 DP 테이블을 만들어줬다. 그리고 움직이지 않은 경우 최솟값은 float('inf')로 만들어 추후 더 작은 값으로 갱신할 수 있도록 했다.

MAX_STEP, INF = 141, float("inf")
# dp[a][b] = c, a칸을 점프해서 b칸으로 가는 최소 움직임은 c번이다
dp = [[INF] * (N + 1) for _ in range(MAX_STEP + 1)]

전체 코드

import sys

# print = sys.stdout.write
input = sys.stdin.readline
# f = open("input.txt", "rt")
# input = f.readline

# N(N + 1) = 20_000
# 141 * 142 = 20_022
MAX_STEP, INF = 141, float("inf")
N, M = map(int, input().split())
small_stones = set()  # 밟을 수 없는 칸

# dp[a][b] = c, a칸을 점프해서 b칸으로 가는 최소 움직임은 c번이다
dp = [[INF] * (N + 1) for _ in range(MAX_STEP + 1)]

def main():
    while row := input().split():
            small_stones.update(map(int, row))
    if 2 not in small_stones:
        dp[1][2] = 1  # 1번째 돌에서 1칸을 움직인 상태로 2번째 돌로 이동

    for i in range(2, N + 1):
        for j in range(1, MAX_STEP + 1):
            if not can_step_on(i) or not dp[j][i]:
                continue
            # j - 1칸 움직일 수 있으면
            if can_move(i, j - 1):
                dp[j - 1][i + j - 1] = min(dp[j][i] + 1, dp[j - 1][i + j - 1])
            # j칸을 움직일 수 있으면
            if can_move(i, j):
                dp[j][i + j] = min(dp[j][i] + 1, dp[j][i + j])
            # j + 1칸을 움직일 수 있으면
            if can_move(i, j + 1):
                dp[j + 1][i + j + 1] = min(dp[j][i] + 1, dp[j + 1][i + j + 1])

    ans = INF
    for i in range(1, MAX_STEP + 1):
        ans = min(ans, dp[i][N])

    print(ans if ans != INF else -1)

def can_move(i, step):
    # 최소 한 칸 이상 움직일 수 있고 step만큼 움직였을 때 최대 N칸 이하일 경우만
    return 0 < step <= MAX_STEP and i + step <= N and can_step_on(i + step)

def can_step_on(idx):
    return idx not in small_stones

if __name__ == "__main__":
    main()