【Algorithm】 [백준] 16549 숨바꼭질 3
문제는 다음과 같습니다.
https://www.acmicpc.net/problem/13549
수빈이는 *2배를 0초만에 갈 수 있다.
수빈이는 +1 -1을 각각 1초만에 갈 수 있다.
문제 풀이 - dynamic programming
- 0부터 N까지 먼저 채워놓고, N부터 차근차근 하나씩 앞으로 나가면서 해당 자리에 오는데 걸리는 최단시간을 찾는다.
def fineMaxTime(N,K):
MaxTime = K-N
i = 2
while(1):
dist = K - N*i
if MaxTime <= abs(dist) :
max_num_list = N*(i) if N != 0 else K+10 # 0문제 해결
return MaxTime, max_num_list
i += 1
def findtime(N,K):
if N >= K :
return (N-K)
Maxtime, max_num_list = fineMaxTime(N,K)
lst = [Maxtime+1] * (max_num_list+1)
# complex case
for i in range(N+1):
lst[N-i] = i
for i in range(N+1, max_num_list+1):
if i % 2 == 1:
lst[i] = lst[i-1]+1
else :
if lst[i-1]+1 > lst[i//2]: # /연산을 해서 나오는 것의 자료형은 무조건 float
lst[i] = lst[i//2]
for j in range(1,100000): # 뒤를 보고 숫자가 너무 크면 줄여준다.
if lst[i-j] > lst[i-j+1]+1:
lst[i-j] = lst[i-j+1]+1
else : break
else : lst[i] = lst[i-1]+1
return lst[K]
if __name__ == "__main__":
N, K = map(int, input().split())
print(findtime(N,K))
문제 풀이 - deque
que알고리즘을 사용한다
dist에 그 위치에 가는데 걸리는 시간을 계산한다.
원래 큐는 오른쪽에서 들어가서 오른쪽에서 나온다.(first input first output)
deque를 사용해서 스택과 큐를 동시에 사용할 수 있다.
deque(double-ended queue) 설명 :
https://excelsior-cjh.tistory.com/96
https://godoftyping.wordpress.com/2015/04/24/python-%EB%8D%B0%ED%81%ACdeque/
from collections import deque
MAX = 100000
N, K = map(int, input().split())
q = deque()
dist = [-1] * MAX * 2
dist[N] = 0
q.append(N)
solution_second = None
while q:
x = q.popleft()
if x == K:
solution_second = dist[K]
break
for op in (x, 1, -1):
nx = x + op
if 0 <= nx < MAX * 2 and dist[nx] == -1:
if op == x:
dist[nx] = dist[x]
q.appendleft(nx)
else:
dist[nx] = dist[x] + 1
q.append(nx)
