[알고리즘] 크래프톤 정글 3주차 / 알고리즘 中 혼자서 못 푼 문제 정리 10(점프)

BOJ 2253 점프

난이도 : (크래프톤 정글 기준) 상, (백준 난이도 기준) 골4

사용 알고리즘 or 자료 구조 : 다이나믹 프로그래밍

 

처음 생각한 풀이

처음에는 돌의 개수만큼의 길이를 가진 1차원 배열을 선언한 뒤, 건널 수 없는 돌의 인덱스에는 False 값을 할당해 밟을 수 없도록 했다.

 

그 후, 1번 돌부터 도착해야할 n번 돌까지 해당 돌까지 오는데 걸린 최소 횟수를 저장해서 마지막 돌까지 도착하도록 풀었다.

 

역시나 풀면서 허점을 느꼈던 만큼, 이 풀이로 80퍼까지밖에 가지 못했다.

 

반례를 찾아보니 어떤 돌까지 최소 횟수로 오면 끝에 도달하지 못하는 경우가 있고, 최소 횟수가 아닌 경우로 왔을 때 끝에 도달하는 경우가 있었다.

 

그래서 시간 초과를 각오하고 돌에 올 수 있는 최대 횟수를 정해놓고 세로 : 돌의 개수, 가로 : 횟수 로 2차원 배열을 선언해 각 횟수 마다 몇의 속도로 오는지를 저장해 일일이 비교해가며 풀었다.

 

정답은 나왔지만 역시나 시간 초과.

 

몇시간을 봤지만 올바른 풀이가 떠오르지 않아 풀이를 찾아봤다.

구글링 이후 풀이

이 문제도 생각보다 풀이가 간단했다.

 

중간에 동료에게서 힌트를 들었는데 처음에는 그 힌트를 이해하지 못했지만, 풀이를 보니 이해가 됐다.

 

2차원 배열을 선언하는 것까지는 맞는데 돌의 개수와 끝지점에 도착할 수 있는 최대 속도로 선언해야했다.

 

예를 들어 돌이 8개라 하자.

 

만약 중간에 한번도 속도를 줄이지 않고 마지막에 도착한다고 가정하면, 등차수열의 합 공식을 이용하여

인 n을 구하면 n이 최대 속도가 되는 것이다.

 

만약 위와 같은 식을 통해 정확한 정수 n이 나오지 않는다면 최대 속도를 다음과 같은 수식으로 계산하면 된다.

속도는 반드시 정수형으로 나와야하기 때문에 수학적으로 생각해봤을 때, n을 무한대로 보냈을 때 최대 속도를 위와 같이 계산해도 수식이 성립함을 알 수 있다.

 

위의 값들을 이용하여 배열을 선언한 이후에는 dp[ i ][ j ] (i번째 돌에 j만큼의 속도로 왔을 때 최소 횟수)라고 보고 풀면 된다.

 

점화식을 만들면 다음과 같다.

 

i - j에 j - 1의 속도, j의 속도, j + 1의 속도로 도착했을 때 모두 속도 j로 i에 도착할 수 있기 때문에 위와 같은 점화식이 나온다.

 

 

 

 

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

 

 

 

 

코드

import sys

N, M = map(int, sys.stdin.readline().split())

maxnum = int((2 * N) ** 0.5)    # 최대로 움직일 수 있는 칸 수

rockb = [[int(1e9) for _ in range(maxnum + 2)] for _ in range(N + 1)]   # rockb[i][j] : i번째 돌로 v의 속도로 왔을 때의 최소값

cant = [int(sys.stdin.readline()) for _ in range(M)]

rockb[1][0] = 0

for i in range(2, N + 1):

    if i in cant:

        continue

    for j in range(1, int((2 * i) ** 0.5) + 1):

        rockb[i][j] = min(rockb[i - j][j - 1], rockb[i - j][j], rockb[i - j][j + 1]) + 1

        # i - j번째 돌에 j - 1, j, j + 1의 속도로 왔으면 각각 j의 속도로 i로 올 수 있음

if min(rockb[N]) >= int(1e9):

    print(-1)

else:

    print(min(rockb[N]))