1. 백준 2253 점프

문제에서 원한는대로 dp 테이블을 정의해보자.
dp[i] = i번째 돌에 도착했을 때 필요한 최소 점프 횟수

이 점화식을 가지고 문제를 풀다보면 현재 속도에 대한 정보가 없기 때문에 풀리지 않는다는 것을 알 수 있다. 따라서 2차원 테이블을 만들고 다음과 같이 정의하였다.

dp[i][j] = j속도로 i번째 돌에 도착했을 때의 최소 점프 횟수

특정 예시를 들어보자.
dp[7][3]의 경우 3의 속도로 왔다는 건 이전에 2, 3, 4의 속도여야 한다는 말이다. 또한 3의 속도로 7에 도착한 것이므로 4번째 돌에서 출발해야 한다. 따라서 다음과 같은 점화식을 뽑아낼 수 있다.

dp[7][3] = min(dp[4][2], dp[4][2], dp[4][4]) + 1

그리고 이때 N <= 10000 이므로 dp 테이블을 N*N으로 하게 된다면 메모리 초과가 일어나게 된다. 따라서 j의 경우 가속을 최대로 했을 때 다음과 같은 식이 성립할 수 있다.
$\sum_{j=1}^{N} j + 1$ >= 10000 인 시점을 찾으면 된다. 값은 대충 150으로 잡으면 널널하게 10000보다 큰 값을 찾을 수 있다.

최종적으로 다음과 같은 코드를 작성할 수 있게된다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [int(input().strip()) for _ in range(m)]
INF = float('inf')
dp = [[INF] * 152 for _ in range(n+1)]

if 2 in arr:
    print(-1)
    exit(0)

dp[2][1] = 1

for i in range(3, n+1):
    if i in arr: continue
    for j in range(1, min(i, 150)):
        dp[i][j] = min(dp[i-j][j-1], dp[i-j][j], dp[i-j][j+1]) + 1

if min(dp[n]) == INF:
    print(-1)
else:
    print(min(dp[n]))

3시간 정도 LLM의 도움 없이 고민의 고민한 결과 풀 수 있었던 점에서 너무 뿌듯한 하루였다...!

2. 이력서 작성

내일 커피챗 시간에 코치님께 피드백 받으려고 오늘 급하게 이력서를 작성했다.. 경력이 넘사인 코치님들께 많이 여쭤보고 다듬을 수 있어야겠다!