[99클럽 코테 스터디 19일차 TIL + DP] 28069 김밥천국의 계단 파이썬

오늘의 학습 키워드

DP

공부한 내용 본인의 언어로 정리하기

문제

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

코드

n, k = map(int, input().split())
for _ in range(k):
    if n % 3 < 2:
        n = min(n-1, n//3 * 2 + n % 3)
    else:
        n -= 1
    if n <= 0:
        break
print('minigimbob' if n <= 0 else 'water')

 

도달하고 싶은 k값부터 역으로 출발하여 n % 3이 2가 되지 않는다면 계단 한칸 내려가기와 마법을 써서 계단 내려가기 둘 중 하나를 선택하고, 되지 않으면 -1만 하며 계단을 내려간다. k번 계단을 내려간 후 만일 내려갔다면 minigimbob을 출력하고, 아니면 water를 출력한다. 

오늘의 회고

처음에는 bfs 방식으로 문제를 해결하려고 노력했었다. 

from collections import deque

n, k = map(int, input().split())
visited = [[0] * (k+1) for _ in range(n+1)]
start = 0

def bfs(start, count):
    q = deque()
    count = 0
    q.append((start, count))
    visited[start][count] = 1

    while q:
        now, count = q.popleft()

        for i in [1, now + now // 2]:
            new = now + i

            if new > n or count + 1 > k:
                continue

            if new == n and count+1 == k:
                print('minigimbob')
                return

            if visited[new][count + 1] == 0:
                visited[new][count + 1] = 1
                q.append((new, count + 1))

    print('water')

bfs(start, 0)

 

해당 방식으로 새로운 값과 진행 회수를 넘겨주며 dfs를 진행하고 이를 2차원 배열에 저장하니 작은 값은 괜찮았지만 큰 값에는 메모리 초과가 일어나는 현상이 발생했다. 그래서 결국 dp로 다시 해결하느라 시간이 2배로 걸렸다. 

또 느낀점은 참 dp는 자주 쓰인다는 점이고, 내가 또 못한다는 점이다. dp를 열심히 연습해야겠다.