[WEEK04] 31일차. 점프, 외판원 순회

몸살 기운이 살짝 있어서 컨디션이 좋지 않지만 힘내보자.

백준 2253 점프

문제 풀러가기

1번 돌멩이부터 N번 돌멩이까지 돌멩이를 밟고 가는 문제이다. 가는 길에 작은 돌은 밟을 수 없다.

최소한의 점프로 갈 수 있는 횟수를 구해야하는 문제다.

링크

위 링크의 글을 참고하였다.

import sys
from math import inf
N, M = map(int, sys.stdin.readline().split())
dp = [[inf] * (int((2 * N)**0.5) + 2) for _ in range(N + 1)] 
dp[1][0] = 0

stone_set = set()
for _ in range(M):
    stone_set.add(int(sys.stdin.readline()))
for i in range(2, N + 1):
    if i in stone_set:
        continue
    for j in range(1, int((2 * i) ** 0.5) + 1):
        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]))

백준 2098 외판원 순회

문제 링크

다음 글을 참고하였다.
비트 마스킹에 대해 좀 더 공부가 필요할 것 같다.

참고 글