https://www.acmicpc.net/problem/2253
시간 2초, 메모리 128MB
input :
- N, M(2 ≤ N ≤ 10,000)(0 ≤ M ≤ N-2)
- M은 크기가 맞지 않는, 즉 크기가 작은 돌의 개수
- 크기가 작은 돌들의 번호가 주어진다.
output :
- 최소의 점프 횟수를 출력한다. 만약 N번 돌까지 점프해갈 수 없는 경우에는 -1을 출력
조건 :
- 이동은 앞으로만 할 수 있다. 즉, 돌 번호가 증가하는 순서대로만 할 수 있다.
- 제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못한다. 즉, 1번 돌에서 2번 돌이 있는 곳으로 점프할 수 있다.
그 다음부터는 가속/감속 점프를 할 수 있는데, 이전에 x칸 점프를 했다면, 다음번에는 속도를 줄여 x-1칸 점프하거나, x칸 점프하거나, 속도를 붙여 x+1칸 점프를 할 수 있다. 물론 점프를 할 때에는 한 칸 이상씩 해야 한다. - 각 돌들은 각기 그 크기가 다르고, 그 중 몇 개의 돌은 크기가 너무 작기 때문에 당신은 그러한 돌에는 올라갈 수 없다.
위의 분의 풀이가 없었다면 이해를 못 하지 않았을 까 생각한다.
여러 다양한 풀이를 보면서 큐를 이용하려고도 하고, dfs를 이용하려고도 했지만 직관적으로 딱 이해가 가기 쉬운것이 점화식이었다.
언젠가부터 점화식을 생각하기 보다 dfs(재귀)를 이용하는 경우를 많이 생각하곤 했는데, 다시 한번 생각하는 계기가 되었다.
아무튼, 현재 위치 i 에 v의 속도를 가지고 왔을 경우 이렇게 올 수 있는 방법은 3가지가 존재한다.
- i - v 에서 감속을 하며 올때. -> [i - v][v + 1]
감속을 했기 떄문에 v + 1을 찾아감. - i - v 에서 속도를 유지 하고 올 때.-> [i - v][v]
속도를 그대로 유지했기 떄문에 v의 값을 찾음. - i - v 에서 가속을 하며 올때. -> [i - v][v - 1]
가속을 하며 왔기 떄문에 v - 1을 찾아감.
dp[i][v] = min(dp[i - v][v - 1], dp[i - v][v], dp[i - v][v + 1]) + 1그리고 만난 벽이 이걸 어떻게 기록하게 할 것인가... 였는데
생각보다 싱거운것이 그냥 모든 경우를 보는 것이었다. dp가 완전 탐색이랑 다를게 뭐가 있나 싶긴 했음...
암튼 여기서 또 부딪힌것은.... 그렇다면 dp 배열을 어떻게 선언해야 하는 것인가 인데 최대 속도로 N이 10000일 때를 생각 할 경우.
속도는 1, 2, 3, 4 ... 순서로 증가한다 이를 통해 합 공식을 가져 올 수 있고, 이를 계산해 보면 (141 * 142) / 2 한 것이 1만을 넘기에
141이 최대 크기라는 것을 알 수 있다.
dp = [[float('inf')] * 142 for i in range(n + 1)]그리고 나서 하나더. 위의 식을 보면 우리는 i - v를 계산한다.
이 때 v가 i 보다 큰 경우가 발생하면 안 되므로, 각 위치에서의 최대 속도를 구해서 그 값까지만 반복을 하도록 하여야 한다.
v = 1
while v * (v + 1) <= 2 * i:
dp[i][v] = min(dp[i - v][v - 1], dp[i - v][v], dp[i - v][v + 1]) + 1
v += 1import sys
n, m = map(int, sys.stdin.readline().split())
data = dict()
for i in range(m):
temp = int(sys.stdin.readline())
data[temp] = 1
dp = [[float('inf')] * 142 for i in range(n + 1)]
dp[1][0] = 0
for i in range(2, n + 1):
if data.get(i):
continue
v = 1
while v * (v + 1) <= 2 * i:
dp[i][v] = min(dp[i - v][v - 1], dp[i - v][v], dp[i - v][v + 1]) + 1
v += 1
ans = min(dp[n])
print(-1 if ans == float('inf') else ans)
