동적 프로그래밍 : 점프(백준 2253번)

▶ 문제 : https://www.acmicpc.net/problem/2253

2253번: 점프

##### 문제 #####
# N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 
# 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 
# 당신은 현재 1번 돌 위에 있는데, 
# 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 한다. 
# 이때 다음 조건들이 만족되어야 한다.
# 이동은 앞으로만 할 수 있다. 
# 즉, 돌 번호가 증가하는 순서대로만 할 수 있다.
# 제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못한다. 
# 즉, 1번 돌에서 2번 돌이 있는 곳으로 점프할 수 있다. 
# 그 다음부터는 가속/감속 점프를 할 수 있는데, 이전에 x칸 점프를 했다면, 
# 다음번에는 속도를 줄여 x-1칸 점프하거나, x칸 점프하거나, 속도를 붙여 x+1칸 점프를 할 수 있다. 
# 물론 점프를 할 때에는 한 칸 이상씩 해야 한다.
# 각 돌들은 각기 그 크기가 다르고, 
# 그 중 몇 개의 돌은 크기가 너무 작기 때문에 당신은 그러한 돌에는 올라갈 수 없다.
# 위와 같은 조건들을 만족하면서 1번 돌에서 N번 돌까지 점프를 해 갈 때, 
# 필요한 최소의 점프 횟수를 구하는 프로그램을 작성하시오.

##### 입력 #####
# 첫째 줄에 두 정수 N, M(0 ≤ M ≤ N-2)이 주어진다. 
# M은 크기가 맞지 않는, 즉 크기가 작은 돌의 개수이다. 
# 다음 M개의 줄에는 크기가 작은 돌들의 번호가 주어진다. 
# 1번 돌과 N번 돌은 충분히 크기가 크다고 가정한다.

##### 출력 #####
# 첫째 줄에 필요한 최소의 점프 횟수를 출력한다. 
# 만약 N번 돌까지 점프해갈 수 없는 경우에는 -1을 출력한다.

 

▶ 접근 방법

DP 테이블 구성이 굉장히 어려웠던 문제였다.
문제에서 주어진 정보를 테이블에 적용하는 연습이 많이 필요할 것 같다.

 

▶ 풀이 코드

import sys

# N : 최종 돌의 숫자, M : 착지할 수 없는 작은 돌의 갯수
N, M = map(int, sys.stdin.readline().split())

# DP 테이블(행은 단계별 돌의 숫자, 열은 속도)
# DP[i][j]의 의미는 i번째 돌에 j의 속도로 도착할 때의 점프 횟수
# 초깃 값은 'inf'로 설정한다.
# 최대 속도는 1부터 N까지 속도를 1씩 늘려간다고 했을 때의 근사 값이다.
DP = [[float('inf')] * (int((2 * N) ** 0.5) + 2) for _ in range(N + 1)]
DP[1][0] = 0

# 착지할 수 없는 돌들을 set에 넣어준다.
passing = set(int(sys.stdin.readline().rstrip()) for _ in range(M))

# 돌을 단계별로 하나씩 늘려간다.
for num_stone in range(2, N + 1):
    # 도착하려고 하는 돌이 passing에 있으면 넘어간다.
    if num_stone in passing:
        continue
    
    # 해당 돌에 도착할 수 있는 속도를 케이스별로 살펴본다.
    for velocity in range(1, int((2 * num_stone) ** 0.5) + 1):
        # DP[돌][속도]는 해당 돌에 도착하기 전 단계를 고려해야한다.
        # 즉, 이전 단계의 속도보다 1 감속한 경우이거나, 이전 단계와 속도가 같은 경우이거나, 이전 단계보다 속도를 1 가속한 경우이다.
        DP[num_stone][velocity] = min(DP[num_stone-velocity][velocity-1], DP[num_stone-velocity][velocity], DP[num_stone-velocity][velocity+1]) + 1

if min(DP[N]) == float('inf'):
    print(-1)
else:
    print(min(DP[N]))

 

▶ 관련 링크

2021.11.25 - [알고리즘] - 동적 프로그래밍(Dynamic Programming)이란?

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 피보나치 수 2(백준 2748번)

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 01타일(백준 1904번)

2021.11.26 - [알고리즘] - 동적 프로그래밍 : 평범한 배낭(백준 12865번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 동전(백준 9084번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : LCS(백준 9251번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 가장 긴 증가하는 부분 수열(백준 11053번)