다이나믹 프로그래밍+BFS+그리디 - 정확히 K번만에 목표에 도달할 수 있는가?

1. 문제

 

28069번: 김밥천국의 계단 (acmicpc.net)

28069번: 김밥천국의 계단

 

 

2. 풀이1

 

그냥 보면 두가지 행동중 하나를 할 수 있는 전형적인 BFS문제

 

1) 한칸을 올라간다

 

2) $\left \lfloor \frac{i}{2} \right \rfloor$만큼 올라간다

 

0번부터 시작한다고 명시되어 있으니 BFS처럼 풀어보면..

 

정확히 K번 행동해야하면서 매 행동마다 queue의 길이만큼 순회시키는데

 

해당 좌표 i가 i+1과 i+i//2를 이동할 수 있으면 queue에 넣어주고..

 

K번 행동한 후에 n이 queue에 있으면 김밥을 먹을 수 있는거

 

from collections import deque

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

queue = deque([0])

for _ in range(k):
    
    x = len(queue)

    for _ in range(x):
        
        i = queue.popleft()
        
        if i+1 <= n:

            queue.append(i+1)

        if i+i//2 <= n:
            
            queue.append(i+i//2)
        
if n in queue:
    
    print("minigimbob")

else:
    
    print("water")

 

 

근데 이렇게 하면 시간초과나더라

 

왜 그런지 생각해보면 의외로 간단하다

 

0번부터 시작했을때 각 행동마다 어디에 위치할 수 있는지 생각해본다면..

 

0번에서 첫번째 행동으로 1번 계단, 두번째 행동으로 0번 계단 그대로

 

1번의 행동으로 0 1에 있을 수 있다.

 

다시 0,1에서 각 행동으로 어디에 있을 수 있는지 생각해보면..

 

0번에서 첫번째 행동으로 1번계단, 두번째 행동으로 0번 계단 그대로

 

1번에서 첫번째 행동으로 2번계단, 두번째 행동으로 1번 계단 그대로

 

0에서 2번의 행동으로 0 1 2에 있을 수 있다.

 

다시 0,1,2에서 각 행동으로 어디에 있을 수 있는지 생각해보면..

 

0번에서 첫번째 행동으로 1번계단, 두번째 행동으로 0번 계단 그대로

 

1번에서 첫번째 행동으로 2번계단, 두번째 행동으로 1번 계단 그대로

 

2번에서 첫번째 행동으로 3번계단, 두번째 행동으로 3번 계단

 

0에서 3번의 행동으로 0 1 2 3에 있을 수 있다.

 

이런식으로 반복해보면...

 

0 1

0 1 2

0 1 2 3

0 1 2 3 4

0 1 2 3 4 5 6

0 1 2 3 4 5 6 7   9

...

 

핵심은 k번째 행동마다 이전 k-1번째 행동에 도착했던 좌표들에 또 도착할 수 있다는 점이다.

 

그러니까 아무런 처리를 하지 않으면 이전에 도착했던 좌표에서 동일한 연산을 반복적으로 수행하니 시간초과가 남 

 

또한 이전에 이미 도착했던 좌표들에서는 굳이 연산을 하지 않더라도 다음에 어디에 도착할지 좌표들을 알 수 있다

 

무슨 말이냐면

 

0 1 2 3에서 연산 후에

 

0 1 2 3 4에 도착했을때, 다음에 어디에 위치할지는 0,1,2,3은 연산하지 않고 새로 도착한 4에서만 연산해보더라도

 

4에서 5번과 6번에 도달할 수 있으니 전체적으로는

 

0 1 2 3 4 5 6에 도달할 수 있다는 것을 알 수 있다.

 

따라서 BFS로 문제를 해결하고 싶다면, 이미 도착했던 좌표들은 visited로 방문처리를 해서

 

다음 행동에 이전에 도착했던 좌표들에서는 동일한 연산을 하지 않도록 한다

 

K번 행동하고 나서 마지막에 visited[n] = 1이면 김밥을 먹을 수 있고, 1이 아니면 김밥을 먹을 수 없다

 

from collections import deque

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

queue = deque([0])

visited = [0]*(n+1)

visited[0] = 1

for _ in range(k):
    
    x = len(queue)

    for _ in range(x):
        
        i = queue.popleft()

        if i+1 <= n and visited[i+1] == 0:
            
            queue.append(i+1)
            visited[i+1] = 1
        
        if i+i//2 <= n and visited[i+i//2] == 0:
            
            queue.append(i+i//2)
            visited[i+i//2] = 1

if visited[n] == 1:
    
    print("minigimbob")

else:
    
    print("water")

 

 

3. 풀이2

 

다이나믹 프로그래밍으로 풀어볼려고 한다면, 이 문제에서 요구하는 사항이 "정확히 K번만에" n번째 계단에 도달할 수 있는가? 여부를 묻고 있어서

 

생각보다 쉽지가 않다

 

일반적인 dp 접근으로는 n번째 계단에 최소횟수로 도달할 수 있는 방법을 구하는거라서..

 

근데 조금만 관찰해보면 생각보다 쉽게 해결할 수 있다.

 

이 문제를 해결하는 핵심 원리는 0번 계단과 1번 계단에서는 두번째 지팡이를 두드리는 행동을 하더라도, 그 자리에 머무른다는 점이다.

 

따라서 0번 계단과 1번 계단에서 내가 원하는 만큼 그 자리에 머무르고,

 

목표로 하는 n번 계단에 도달하게 만들 수 있다.

 

dp[i]를 i번째 계단에 도달할때, 이동하는 최소 횟수라고 정의하자.

 

0번부터 시작하니 dp[0] = 0으로 초기화하고, 나머지는 INF로 초기화한다.

 

i번째 계단에서 i+1번째 계단으로 올라갈 수 있는 경우는 dp[i]+1과 dp[i+1]의 최솟값이다.

 

i번째 계단에서 i+i//2번째 계단으로 올라갈 수 있는 경우는 dp[i]+1과 dp[i+i//2]의 최솟값이다.

 

이런식으로 n번 계단에 도달할 수 있는 최솟값을 dp[n]으로 구해놓는다면...

 

0번 계단에서 K-dp[n]만큼 지팡이를 두드리는 행동을 하고, dp[n]으로 n번째 계단에 이동한다면

 

정확히 K번만에 n번째 계단에 도달할 수 있게 된다.

 

따라서, dp[n]이 K보다 크다면 K번만에 n번째 계단에 도달할 수 없고,

 

K보다 작다면, K-dp[n]만큼 지팡이를 두드리고 n번째 계단으로 이동하면 된다.

 

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

INF = 1000000000000000000000000000000

dp = [INF for _ in range(n+1)]
dp[0] = 0

for i in range(n):
    
    dp[i+1] = min(dp[i]+1,dp[i+1])

    if i+i//2 <= n:
        
        dp[i+i//2] = min(dp[i]+1,dp[i+i//2])

if dp[n] <= k:
    
    print("minigimbob")

else:
    
    print("water")

 

4. 풀이3

 

위의 DP 방식은 0번째 계단에서 원하는 만큼 지팡이를 두드리고, 가장 빠르게 n번째 계단으로 올라갈 수 있는지 생각하는건데

 

역으로 n번째 계단에서부터 시작해서 매 순간 가장 빠르게 내려가서 0번째 계단에 도달할 수 있다면,

 

거기서 나머지를 모두 지팡이를 두드리는 행동에 소비하면 되니까, 그런 경우를 체크한다면 더 빠르게 풀수 있다.

 

근데 n번째 계단에서 내려가는 방법을 구하는게 생각보다 힘든데

 

i번째 계단에서 지팡이를 두드리는 행동으로 n번째 계단으로 올라간다면.. 그 때의 i를 어떻게 구할까?

 

그러니까 $$i + \left \lfloor \frac{i}{2} \right \rfloor = n$$을 만족하는 i를 구해야한다.

 

잘 모르겠으면 하나하나 써보자

 

i = 0이면 n = 0

 

i = 1이면 n = 1

 

i = 2이면 n = 3

 

i = 3이면 n = 4

 

i = 4이면 n = 6

 

i = 5이면 n = 7

 

i = 6이면 n = 9

 

...

 

i가 짝수인가 홀수인가에 따라

 

i = 2k이면 i = 2n/3

 

i = 2k+1이면 i = (2n+1)/3 

 

n과 i의 관계식이 위와 같이 구해진다.

 

따라서 n부터 시작해서 내려갈 수 있는 경우는 x1 = n-1

 

x2 = 2n//3 아니면 x2 = (2n+1)//3이다.

 

근데 x2는 정수이므로, n이 3의 배수라면 x2 = 2n//3으로 하고

 

n이 3의 배수가 아니고 2n+1이 3의 배수이면 x2 = (2n+1)//3으로 한다.

 

근데 보면 알겠지만 n과 i가 일대일 대응은 아니다.

 

예를 들어 n = 2일때 만족하는 i가 존재하지 않는다.

 

즉 n이 3의 배수도 아니고 2n+1이 3의 배수도 아니면 x2가 존재하지 않는다. 

 

이는 오직 첫번째 행동인 1칸 올라가는 행동만으로 n번째 계단에 올라갈 수 있다는 뜻이다.

 

그래서 그런 경우에는 x2도 n-1로 한다.

 

그리고 다음 n을 x1과 x2의 최솟값으로 갱신해서 매 순간 가장 빠르게 내려가는 전략을 취한다.

 

k번의 반복문을 도는 동안 n=0이 된다면 나머지는 지팡이를 도는 행위로 원하는 만큼 횟수를 소모할 수 있으니 김밥을 먹고 바로 반복문 탈출

 

하지만 반복문을 탈출하더라도, n이 0이 아니라면 k번만에 n번째 계단에 도달할 수 없다는 뜻이다.

 

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

for _ in range(k):
    
    x1 = n-1

    if n % 3 == 0:
        
        x2 = 2*n//3
    
    elif (2*n+1) % 3 == 0:
        
        x2 = (2*n+1)//3
    
    else:
        
        x2 = n-1
    
    n = min(x1,x2)
    
    if n == 0:
        
        print("minigimbob")
        break

if n != 0:
    
    print("water")