백준 2253 점프

점프 (백준 2253)

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

점화식을 세우는 방법에 대하여 배울 수 있는 문제였고,
동시에 dp의 적용법에 대하여도 배울 수 있었다

점화식의 경우,
‘수학적 귀납법’의 방식을 따라가듯 세우는 것이 일반적
=> ‘재귀’ 함수를 만드는 것과 비슷하다

n = 0 일때를 확인하며,
이후 수를 점차적으로 늘려나가며,
i… i+1 을 증명할 수 있는 공식을 발견해나가는 방식이라 한다

dp의 적용법의 경우,
먼저 문제에 대한 ‘해결법’을 먼저 확인한 후,
‘중복 계산’을 피할 수 있는 방식을 생각해보는 것이다

물론 그 과정에서 ‘최적 부분 구조’를 통해
문제를 ‘분할할 수 있나’를 확인해야 한다

피보나치 수열의 경우,
-> ‘재귀’로 풀어 fibo(n-1) + fibo(n-2)를 적용하면 되겠다!
=> 해당 값을 dp 배열에 저장하여 이후, 같은 함수 호출 시 반환

또한, ‘점화식’을 명확히 세울 수 있다면,
bottom-up 으로 속도상의 이득을 챙기고,
그렇지 않다면 top - down 방식을 이용하여,
먼저 구현을 해보는 방식을 생각하는 것이다

Code

import sys
import math
sys.setrecursionlimit(10**8)

inp = sys.stdin.readline

num,dNum = map(int,inp().split())

dList = []

for i in range(dNum):
    dList.append(int(inp().strip()))

# 한 번에 뛸수 있는 최대 거리는
# sqrt() num * 2 ) + 1
max_speed = int((2*num) **0.5) + 1
dp = [[math.inf for _ in range(max_speed + 1)] for _ in range(num+1)]

# 시작점 초기화
dp[1][0] = 0

for step in range(2,num+1):
    if step in dList:
        continue

    for speed in range(1,max_speed):
        dp[step][speed] = min(dp[step-speed][speed - 1],
                              dp[step-speed][speed],
                              dp[step-speed][speed + 1]) + 1

result = min(dp[num])

if result == math.inf:
    print(-1)
else:
    print(result)

해결 아이디어

1. dp[i][v] 를 ‘i’번째 돌에 ‘v’번째 속도로 도착하는 경우 중,
   최소 점프 횟수를 저장한다
2. dp[i][v]에 v의 속력으로 도착하는 경우의 수는
   ‘dp[i-v][v-1] 에서 v+1로 가속해 옴’
   ‘dp[i-v][v] 에서 동일한 v로 옴’
   ‘dp[i-v][v+1] 에서 v-1로 감속해 옴’
   
3. 따라서 점화식은 dp[i][v] = min(dp[i-v][v-1]
   ,dp[i-v][v]
   ,dp[i-v][v+1]
   )+1
4. 초기값(1,0) 설정 : 1번째 돌에서 0번째 속도로 시작
   
5. 돌 개수와 속도의 관계는 n = 1 + (v(v+1)/2) 이므로
   가장 빠른 속도의 근사값은
   v ** 2 + v = 2N
   v = (2n - v) ** 0.5 < 2n ** 0.5