https://www.acmicpc.net/problem/1697
난이도에 맞지 않게 굉장히 애를 먹었던 문제.
시간초과 메모리초과 틀렸습니다의 늪에서 허우적거린...^ㅁ^ 풀고 보니 결국 하나를 잘못 생각했다.
풀이 1
[백준] 1463. 1로 만들기 와 비슷하게, DP로 풀 수 있을 것이라 생각했으나, 오답.
아무래도 +1, -1이 둘 다 존재하기 때문에, 수가 계속 커지기만 하는 것은 아니라서, 이런 방식으로 풀이하는 것은 불가능한 듯.
N, K = map(int, input().split())
dp = dict()
dp[K] = 0
dp[K*2] = 1
for i in range(K*2, 0, -1):
if i % 2 == 0:
dp[int(i/2)] = min(dp.get(int(i/2), 100000), dp[i]+1)
dp[i+1] = min(dp.get(i+1, 100000), dp[i]+1)
dp[i-1] = min(dp.get(i-1, 100000), dp[i]+1)
print(dp[N])
풀이 2
BFS같은 느낌으로 풀었으나, visit check를 하지 않아서 그런지 메모리 초과가 난다.
from collections import deque
N, K = map(int, input().split())
deq = deque([N])
nowDeq = deq
cnt = 0
isFind = False
while not isFind:
deq = deque([])
while nowDeq:
a = nowDeq.popleft()
if a == K:
print(cnt)
isFind = True
break
deq.append(a*2)
deq.append(a+1)
deq.append(a-1)
cnt += 1
nowDeq = deq
풀이 3
시간초과, 메모리초과의 늪에서 만들어낸 답(?)
visit처리 해주고, 주의할 점은.. indexError 나지 않도록 0~100,000 사이로 조건 걸어줍시다.
from collections import deque
import sys
input = sys.stdin.readline
def sol():
N, K = map(int, input().split())
deq = deque([N])
visit = dict()
visit[N] = 0
while deq:
a = deq.popleft()
if a == K:
print(visit[a])
return
for i in [a*2, a+1, a-1]:
if 0 <= i <= 100000 and visit.get(i, -1) == -1:
deq.append(i)
visit[i] = visit[a]+1
sol()