[DP] 백준 점프 2253번 with Python3 ★★

https://www.acmicpc.net/problem/2253

2253번: 점프

 

문제

 

풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())

max_speed = int((2*n)**0.5) + 1
dp_table = [[float('inf')] * (max_speed+1) for i in range(n+1)]
# dp_table[i][j] / [i] = 돌 번호  [j] = acc

smol_stone = set()

for _ in range(m):
    smol_stone.add(int(input().rstrip()))


dp_table[2][1] = 1

for step in range(3, n+1):
    if step in smol_stone:
        continue
    for speed in range(1, max_speed):
        dp_table[step][speed] = min(dp_table[step - speed][speed - 1],
                                    dp_table[step - speed][speed],
                                    dp_table[step - speed][speed + 1]) + 1

answer = min(dp_table[n])

if answer == float('inf'):
    print(-1)
else:
    print(answer)

출처:https://github.com/emplam27/Python-Algorithm/blob/master/%EB%B0%B1%EC%A4%80/%EB%B0%B1%EC%A4%80_2253_%EC%A0%90%ED%94%84_DP_2%EC%B0%A8%EC%9B%90.py

해설

돌 번호와 가속 혹은 이동하는 칸 수로 테이블을 만들어서 진행하자는 아이디어까지는 구상했었다. 하지만 dp의 특성? 을 고려하지 않고  bfs 처럼 접근해서 자꾸 테이블이 원치 않는 방향의 데이터로 차올랐다. 

 

dp는 기본적으로 부분 문제를 합쳐서 최적해를 찾아내는 것인데 , bfs은 아예 다른 방향이다. bfs는 부분 문제가 아니라 같은 종류의 문제를 위치를 이동하며 반복적으로 푸는 느낌?

 

아무튼 구현 단계에서 막혀서 내 아이디어의 방향과 유사한 답을 참고하여 구현에 성공했다. 

 

중요 포인트!

DP는 지점 1에서 234 의 경우로 뻗어 나아가는게 아니라 , 지점 1을 위해 2,3,4 의 부분 문제를 해결하고 그 중의 최적을 선택해 지점 1에 넣는다는 것이다. 

 

가장 dp에 대해 이해하는데 도움을 준 문제가 아니었나 싶다.