I am an amazing person.

1 분 소요

1463번 : 1로 만들기

1463: 1로 만들기

방법 1 (틀림)

  • want: 연산 횟수의 최솟값
  • 그리디 알고리즘 냄새가 나지만… 규칙에서 예외적인 경우가 있음 (그리디라면 최대한 큰 수로 나누었을 것)

=> 다양한 경우로 접근해서 최솟값을 따져봐야 함 (다이나믹 프로그래밍)

import sys
input = sys.stdin.readline

n = int(input())
cnt = 0

# 3으로 나눠 떨어지게 n-- 수행
while n > 3 and n % 3 != 0:
    n -= 1
    cnt += 1

# 최대한 3으로 나누기
while n % 3 == 0:
    n //= 3
    cnt += 1

# 2로 나눠 떨어지게 n-- 수행
while n > 1 and n % 2 != 0:
    n -= 1
    cnt += 1

# 최대한 2로 나누기
while n > 1:
    n //= 2
    cnt += 1

# n이 1이 될 때까지
while n!= 1:
    n -= 1
    cnt += 1


print(cnt)

방법 2 (옳은 풀이)

  • 다이나믹 프로그래밍 - 메모이제이션을 활용해 불필요한 중복 계산을 막아준다
  • Bottum Up 방식
import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * (n + 1) # 1번 idx부터 유의미한 값 다룸

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[n])

참고