BOJ #1463 1로 만들기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #1463 1로 만들기

문제 풀이

특정 숫자 N을 연산하는 데 경우의 수는 세 가지이다. 시간이 0.15초로 제한인 걸 봐선 메모이제이션이 아니라 타뷸레이션으로 진행해야 하지 싶다.

1. 3으로 나누어 떨어질 경우 3으로 나눈다.
2. 2로 나누어 떨어질 경우 2로 나눈다.
3. 1을 뺀다.

• 0으로 초기화된 하위 문제를 저장할 길이가 N + 1인 dp배열 생성
• 2번부터 N까지 초기값은 dp[i - 1] + 1로 설정(연산 방법 3번)하고 3으로 나눌 수 있다면 dp[i // 3] + 1과 비교하고 2로도 나눌 수 있다면 dp[i // 2] + 1과 비교한다. 그 중의 최솟값이 dp[i]가 된다.
• 마지막까지 진행하면 dp[N]를 출력한다.

python 코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [0 for _ in range(N + 1)]
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])