1697 - 숨바꼭질

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

1697번: 숨바꼭질

 

 

- DP

- BFS

 

n, k = map(int, input().split())

dp = [int(1e9)] * 200001
dp[n] = 0

if n == 0:
    dp[1] = 1
    dp[2] = 2
else:
    dp[n-1] = 1
    dp[n+1] = 1
    dp[2*n] = 1

if n >= k:
    print(n-k)
    exit()

for i in range(n+1, k+1):
    if i % 2 == 0:
        dp[i] = min(dp[i-1], dp[i+1], dp[i//2]) + 1
    else:
        dp[i] = min(dp[i-1], dp[i+1]) + 1

print(dp[k])

(DP, 오답)

 

from collections import deque

def bfs(start):
    q = deque([start])
    visited[start] = True
    v = n
    while v != k:
        v = q.pop()

        for i in [v-1, v+1, v*2]:
            if 0 <= i < 200001 and visited[i] == False:
                q.appendleft(i)
                visited[i] = True
                predecessor[i] = predecessor[v] + 1

    print(predecessor[k])

n, k = map(int, input().split())

visited = [False] * 200001
predecessor = [0] * 200001

bfs(n)

(BFS, 정답)

 

처음 보고 DP식이 떠올라서 바로 코드짰는데 틀렸당..

 

원래 알고리즘 분류 안보는 편인데 DP로 세 번인가 제출해도 오답떠서 봤더니 BFS 문제였다

 

BFS 분류 보니 문제는 쉽게 풀렸다

 

 

문제를 처음 볼 때 DP로 푸는 문제인지 BFS로 푸는 문제인지 어떻게 구별하는건가 싶어 구글링했는데, DP는 기본적인 아이디어가 재귀적인 점화식이기 때문에, Ground case가 있어야 된다고 했다!

 

한마디로 재귀가 종료되는 케이스가 존재해야 DP로 풀 수 있다고 한다. 사실 잘 이해는 못 했는데.. 이번 문제는 값이 늘어날 수도 있고, 줄어들 수도 있어서 그런 거 가따~

 

+) 헉 아마 Top-down과 Bottom-up 둘 다 해당하지 않아서 일 것 같다.