[백준/Python] 33677번 푸앙이와 콩나무

문제

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

 

코드

import math
from collections import deque
n = int(input())

data = {}
day = 0
answer = 10**8
water = 0
data[1] = [answer, water]
data[n] = [0,0] # day, water
queue = deque()
queue.append(n)
while queue:
    cur = queue.popleft()
    if n == 0:
        data[1] = [-1, -1]
        break
    if n == 1:
        data[1] = [0, 0]
        break
    if n == 2:
        data[1] = [1, 1]
        break
    
        
    if cur <= 1:
        continue
    data1 = cur - 1
    if data1 in data:
        if data[data1][0] > data[cur][0] + 1:
            data[data1][0] = data[cur][0] + 1
            data[data1][1] = data[cur][1] + 1
            queue.append(data1)
        if data[data1][0] == data[cur][0] + 1 and data[data1][1] > data[cur][1] + 1:
            data[data1][0] = data[cur][0] + 1
            data[data1][1] = data[cur][1] + 1
            queue.append(data1)
    else:
        data[data1] = [data[cur][0] + 1, data[cur][1] + 1]
        queue.append(data1)
            
    if cur % 3 == 0:
        data2 = cur // 3
        if data2 in data:
            if data[data2][0] > data[cur][0] + 1:
                data[data2][0] = data[cur][0] + 1
                data[data2][1] = data[cur][1] + 3
                queue.append(data2)
            if data[data2][0] == data[cur][0] + 1 and data[data2][1] > data[cur][1] + 3:
                data[data2][0] = data[cur][0] + 1
                data[data2][1] = data[cur][1] + 3
                queue.append(data2)
        else:
            data[data2] = [data[cur][0] + 1, data[cur][1] + 3]
            queue.append(data2) 
        
    if math.sqrt(cur) == int(math.sqrt(cur)):
        if not (cur == 1):
            data3 = int(math.sqrt(cur))
            if data3 in data:
                if data[data3][0] > data[cur][0] + 1:
                    data[data3][0] = data[cur][0] + 1
                    data[data3][1] = data[cur][1] + 5
                    queue.append(data3)
                if data[data3][0] == data[cur][0] + 1 and data[data3][1] > data[cur][1] + 5:
                    data[data3][0] = data[cur][0] + 1
                    data[data3][1] = data[cur][1] + 5
                    queue.append(data3)
            else:
                data[data3] = [data[cur][0] + 1, data[cur][1] + 5]
                queue.append(data3) 
# print(data)
print(data[1][0]+1, data[1][1]+1)

 

예쁘게 풀지는 않았지만 . . 

 

dp와 큐를 이용한 풀이입니다. 

n에서 내려가면서 계산하는 탑다운 풀이입니다. 

n - 1, n % 3 == 0이라면 추가적으로 n // 3, n ** 0.5가 정수라면 추가적으로 n ** 0.5을 계산해서 기존 딕셔너리와 비교합니다. 

기존에 있는 값이 없거나, 기존값보다 날짜가 더 빠르다면 갱신해주고 큐에 다시 삽입하여 순회합니다.