1463: 1로 만들기 - Python

문제

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

풀이1 (내 풀이)

n = int(input())
memo = [0, 0]

for x in range(2, n+1):
    arr = [memo[x-1]]
    if x % 6 == 0:
        arr.extend([memo[x//2], memo[x//3]])
    elif x % 3 == 0 :
        arr.append(memo[x//3])
    elif x % 2 == 0:
        arr.append(memo[x//2])
    
    memo.append(min(arr) + 1)

print(memo[n])

• 잘 모르겠어서 GPT한테 힌트 좀 달라고 했다.
• bottom-up 방식으로 구현했다.
• memo[x]: x를 1로 만드는데 필요한 최소 연산 횟수

풀이 2 (adore_voy님 풀이)

n = int(input())
d = [0] * (n+1)

for i in range(2, n+1):
    d[i] = d[i-1] + 1 # 기본 연산
    if i % 3 == 0: # 3으로 나누어 떨어지면 3으로 나누기
        d[i] = min(d[i], d[i//3] + 1)
    if i % 2 == 0: # 2로 나누어 떨어지면 2로 나누기
        d[i] = min(d[i], d[i//2] + 1)
        
print(d[n])

• 풀이 1에서 6으로 나누어 떨어지는지 검사할 필요가 없었다.
• 경외심이 든다.