[PS] BOJ 2253 / 점프

Minjun Kim

24 Jul 2025 • 3 min read

문제 링크: https://www.acmicpc.net/problem/2253

Thumbnail: Photo by Jackson Blackhurst (Unsplash)

처음 봤을 때는 DP로 풀 수 있는 계단 문제를 생각했는데, 오를 수 있는 속도를 변화시킬 수 있어 조금 더 풀이가 까다로웠습니다.

풀이

Bottom-Up 방식의 DP로 접근했습니다.

DP 배열 구상

DP배열은 다음과 같이 정의했습니다.

💡 DP[돌 번호][도달한 속도] = 점프 횟수

돌 번호의 경우, 1부터 N까지의 수를 사용하면 되지만 도달한 속도의 범위가 어디까지일지 가늠이 되지 않아 Map으로 표현했습니다.

1번 돌에서 시작하기 때문에, 1번 돌의 점프 횟수는 0입니다.
또한, 문제 조건에 따라 처음에는 속도 1로 점프해야 하므로 2번 돌의 점프 횟수는 1, 그 때의 속도는 1입니다.

NOT_VISITED = N * 2 # 방문하지 않은 정점임을 표시할 적절한 수
DP = [{} for _ in range(N + 1)]
DP[1][1] = 0
DP[2][1] = 1

DP 배열 초기화

방문할 수 없는 돌 처리

문제에서는 \(M\)개의 방문할 수 없는 돌 번호가 주어집니다. (순서는 정렬되지 않은 상태입니다.)

길이 \(N\)의 배열에 bool값을 저장해도 되고, Map으로 해당하는 돌 번호만 저장해 관리해도 됩니다. 저는 Map을 사용했습니다.

cannot_pass = {}
for _ in range(S):
    cannot_pass[int(input())] = True

방문할 수 없는 돌 번호 입력받기

DP 배열 채우기

이제 DP 배열을 채워야 합니다. Bottom-UP 접근으로, 1번 돌부터 N번 돌까지 올라가면서 DP 배열을 갱신했습니다.

점화식은 다음과 같습니다:

💡 DP[다음 돌 번호][다음 돌 속도]
= min(DP[다음 돌 번호][다음 돌 속도], DP[이번 돌 번호][현재 속도] + 1)

for i in range(2, N):
    if cannot_pass.get(i):
        continue
    for cur_speed in DP[i].keys():
        for next_speed in (cur_speed - 1, cur_speed, cur_speed + 1):
            next_stone = i + next_speed
            if i < next_stone <= N and not cannot_pass.get(next_stone, False):
                DP[next_stone][next_speed] = min(DP[next_stone].get(next_speed, NOT_VISITED), DP[i][cur_speed] + 1)

print(min(DP[N].values()) if len(DP[N]) > 0 else -1)

DP 배열 채우기

시행착오

처음에는 DP 배열을 일차원으로 구성해, 점프 횟수만 기록한 후 속도는 해당 돌에 최소한의 점프로 도달한 경우의 속도 값만 기록해 다음 DP 배열을 채웠습니다.

하지만, 이 경우 놓치게 되는 경우가 존재했습니다. 따라서, DP 배열을 이차원으로 구성해 모든 경우를 기록하며 계산했습니다.

전체 코드

input = open(0).readline
N, S = map(int, input().split())

NOT_VISITED = N * 2 # 방문하지 않은 정점임을 표시할 적절한 수
DP = [{} for _ in range(N + 1)]
DP[1][1] = 0
DP[2][1] = 1

cannot_pass = {}
for _ in range(S):
    cannot_pass[int(input())] = True

for i in range(2, N):
    if cannot_pass.get(i):
        continue
    for cur_speed in DP[i].keys():
        for next_speed in (cur_speed - 1, cur_speed, cur_speed + 1):
            next_stone = i + next_speed
            if i < next_stone <= N and not cannot_pass.get(next_stone, False):
                DP[next_stone][next_speed] = min(DP[next_stone].get(next_speed, NOT_VISITED), DP[i][cur_speed] + 1)

print(min(DP[N].values()) if len(DP[N]) > 0 else -1)

solution.py