[백준] 16549 숨바꼭질 3

문제는 다음과 같습니다. 

https://www.acmicpc.net/problem/13549

 

1. 수빈이는 *2배를 0초만에 갈 수 있다.

2. 수빈이는 +1 -1을 각각 1초만에 갈 수 있다. 

 

문제 풀이 - dynamic programming

1. 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

1. que알고리즘을 사용한다

2. dist에 그 위치에 가는데 걸리는 시간을 계산한다.

 

원래 큐는 오른쪽에서 들어가서 오른쪽에서 나온다.(first input first output)

deque를 사용해서 스택과 큐를 동시에 사용할 수 있다. 

deque(double-ended queue) 설명 :

1. https://excelsior-cjh.tistory.com/96

2. 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)