문제 바로가기
문제:
N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 한다. 이때 다음 조건들이 만족되어야 한다.
- 이동은 앞으로만 할 수 있다. 즉, 돌 번호가 증가하는 순서대로만 할 수 있다.
- 제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못한다. 즉, 1번 돌에서 2번 돌이 있는 곳으로 점프할 수 있다.그 다음부터는 가속/감속 점프를 할 수 있는데, 이전에 x칸 점프를 했다면, 다음번에는 속도를 줄여 x-1칸 점프하거나, x칸 점프하거나, 속도를 붙여 x+1칸 점프를 할 수 있다. 물론 점프를 할 때에는 한 칸 이상씩 해야 한다.
- 각 돌들은 각기 그 크기가 다르고, 그 중 몇 개의 돌은 크기가 너무 작기 때문에 당신은 그러한 돌에는 올라갈 수 없다.
위와 같은 조건들을 만족하면서 1번 돌에서 N번 돌까지 점프를 해 갈 때, 필요한 최소의 점프 횟수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 두 정수 N, M(0 ≤ M ≤ N-2)이 주어진다. M은 크기가 맞지 않는, 즉 크기가 작은 돌의 개수이다. 다음 M개의 줄에는 크기가 작은 돌들의 번호가 주어진다. 1번 돌과 N번 돌은 충분히 크기가 크다고 가정한다.
출력:
첫째 줄에 필요한 최소의 점프 횟수를 출력한다. 만약 N번 돌까지 점프해갈 수 없는 경우에는 -1을 출력한다.
풀이:
이 문제는 못 풀었다.. 따라서 다른 사람의 코드를 보고 이해했다
내 아이디어도 dp에 돌에 도착할 수 있는 가장 작은 경우의 수를 저장하는 것이었는데, 지금 x가 뭐인지를 어떻게 저장해야하는지 몰랐다.
2차원 배열로 해결하면 된다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N, M = map(int, sys.stdin.readline().split())
# 공차가 1 인 등차수열에서 가질 수 있는 최대속도 근사값 선정
# dp = [현재돌][최대속도]
dp = [[float('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]) == float('inf'):
print(-1)
else:
print(min(dp[N]))
# 근사값 선정 방법
# K * (K + 1) / 2 = N
# 최대속도 +1 속도가 0
범위가
첫째항이 1이고 공차가 1인 공차수열 공식
K * (K + 1) / 2 = N
#
(int((2 * N)** 0.5) + 2)
인 이유는 등차수열의 합을 구하는 것이다. 거기에 + 1을 해주는 이유는 0 을 포함하기 떄문에 +1을 해준다.
dp는 2차원 배열로 나온다.
dp[현재돌번호][속도]
속도-1 , 그대로, 속도 +1 을 점화식으로 나타내주면 다음과같다
dp[i][j] = min(dp[i - j][j - 1], dp[i - j][j], dp[i - j][j + 1]) + 1dp[i-j] 현재돌에서 속도만큼 빼준 돌 그리도 뒤에는 그 속도보다 낮춰주거나 올려주거나, 그대로거나 를 계싼한다.
- dp[i][j]는 현재 돌 번호가 i이며 속도가 j일 때, 도착하기 위해 필요한 최소 점프 횟수를 계산
- dp[i - j][j - 1]은 이전 돌 번호인 i - j에서 속도를 j - 1로 줄여서 점프한 경우의 최소 점프 횟수
- dp[i - j][j]는 이전 돌 번호인 i - j에서 속도를 그대로 유지하며 점프한 경우의 최소 점프 횟수
- dp[i - j][j + 1]은 이전 돌 번호인 i - j에서 속도를 j + 1로 증가시켜 점프한 경우의 최소 점프 횟수
만약 dp[2][1] 이면 현재 돌 번호가 2 이며 이전에 한 칸 점프를 했으며 속도가 1이라는 뜻이다.
정답인 dp[19][5] 로 치면
19 번째 돌에 도착하기 위해서 속도 5로 점프해야한다.
14번째에 돌에 도착하기위해 속도 4로 점프해야한다. ... 라는 뜻이다.
체크하고 다시 풀어본다.
댓글