[Algorithm] DP - 백준 1463

오늘은 DP 문제 중 하나인 백준 1463번 문제를 풀어봅시다.

1463

문제 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

결과 : 맞았습니다!!

풀이 시간 : 1시간 미만 성공

코드 비교

나의 코드 (PyPy3)

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
memory = {}

queue = deque([(n, 0)])
while queue:
    now, score = queue.popleft()
    if now in memory and memory[now] <= score:
        continue
    memory[now] = score
    if now == 1: break
    if now % 3 == 0: 
        queue.append((now // 3, score + 1))
    if now % 2 == 0:
        queue.append((now // 2, score + 1))
    queue.append((now - 1, score + 1))

print(memory[1])

랭킹 3위의 코드 (thenitromefan, Python 3)

def operations(number):
    counts = [0] * (number+1)
    for i in range(2, number+1):
        counts[i] = counts[i-1] + 1
        if i % 2 == 0:
            counts[i] = min(counts[i], counts[i//2] + 1)
        if i % 3 == 0:
            counts[i] = min(counts[i], counts[i//3] + 1)
    return counts[number]


print(operations(int(input())))

느낀점

저는 Queue를 활용하여 1이 나올때까지 X를 나누거나 뺐습니다. 이 과정에서 숫자마다 연산 횟수를 기록하여 최소 연산 횟수가 아닐 때 종료시키도록 했습니다. 반면, 랭킹 3위님은 1부터 시작하여 X까지 연산 횟수를 기록하며 올라가는 방식을 선택하셨습니다. 이때, 단순 for 반복문만을 사용하여 제 코드보다 간결한 느낌이 들었습니다. DP만의 코드 빌드업이 무엇인지 이 문제를 통해 배운 것 같습니다.

 

오늘의 글은 여기까지입니다. 감사합니다!