[baekjoon] 백준 1463번(파이썬): 1로 만들기

문제

1463번: 1로 만들기

알고리즘

- dp를 통해 문제를 수행한다.

- 1부터 n까지 반복하여 각 수의 최소 연산 횟수를 구한다.

- 반복문에서 2 부터 n + 1까지 반복한 이유는 1이 되기 위한 연산 횟수는 필요없기 때문이다.

- 1을 빼주는 연산은 현재 연산 횟수를 이전까지에 연산 횟수에서 + 1 해준 연산 횟수로 초기화 해줘 확인한다.

- 현재 3으로 나눠진다면 현재 수를 구하기 위한 연산 횟수와 3으로 나눈 값의 연산 횟수에서 + 1해준 값과 비교하여 작은 값을 현재 연산 횟수로 초기화한다.

- 현재 수가 2로 나눠진다면 현재 수를 구하기 위한 연산 횟수와 2로 나눈 값의 연산 횟수에서 + 1 해준 값과 비교해여 작은 값을 현재 연산 횟수로 초기화한다.

코드

import sys

n = int(sys.stdin.readline())
dp = [0] * (n + 1) # dp 테이블

# 1부터 n까지 각 수를 연산하여 최소 연산 횟수를 구한다.
for i in range(2, n + 1):

    # 1을 빼주는 연산
    # 현재 연산 횟수를 이전까지에 연산 횟수에서 + 1 해준 연산횟수로 초기화한다.
    dp[i] = dp[i - 1] + 1

    # 현재 수가 3으로 나눠진다면
    # 현재 수를 구하기 위한 연산 횟수와 3으로 나눈 값의 연산 횟수에서 + 1 해준 값과 비교하여
    # 작은 값을 현재 연산 횟수로 초기화한다.
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)

    # 현재 수가 2로 나눠진다면
    # 현재 수를 구하기 위한 연산 횟수와 2로 나눈 값의 연산 횟수에서 + 1 해준 값과 비교하여
    # 작은 값을 현재 연산 횟수로 초기화한다.
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)

print(dp[n])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법