[백준/python] 1463번: 1로 만들기

문제

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

1463번: 1로 만들기

---

문제 요약

정수 N이 주어졌을 때, 세 개의 연산을 적절히 사용해서 1을 만들어야한다.
연산을 사용하는 횟수의 최솟값을 출력한다.
 
정수 N에 사용할 수 있는 연산
1. N이 3으로 나누어 떨어지면, 3으로 나눈다.
2. N이 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

---

코드

import sys
input = __import__('sys').stdin.readline

N = int(input())

dp = [1000000] * (N + 1)

if N == 1:
    print(0)
elif N == 2:
    print(1)
elif N == 3:
    print(1)
else:
    dp[1] = 0
    dp[2] = 1
    dp[3] = 1

    for i in range(4, N + 1):
        if i % 2 == 0 and i % 3 == 0:
            dp[i] = min(dp[i // 2], dp[i - 1], dp[i // 3]) + 1
        elif i % 2 == 0:
            dp[i] = min(dp[i // 2], dp[i - 1]) + 1
        elif i % 3 == 0:
            dp[i] = min(dp[i // 3], dp[i - 1]) + 1
        else:
            dp[i] = dp[i - 1] + 1

    print(dp[N])

---

코드 설명

N이 1까지 도달하는 데 필요한 최소 연산 횟수는 1이 N까지 도달하는데 필요한 최소 연산 횟수와 같다.
 
1. N에 3을 곱한다.
2. N에 2를 곱한다.
3. 1을 더한다.

 

1. 다이나믹 프로그래밍을 위해 필요한 메모이제이션 테이블 dp를 생성한다.
+ dp[i]는 i를 세 가지 연산만으로 1에 도달시킬 때 필요한 최소 연산 횟수이다.
 
2. N이 1, 2, 3 인 경우에 대한 예외 처리를 해준다.
 
3. N이 4 이상인 경우, 처음 몇 개의 숫자(1, 2, 3)에 대한 최소 연산 횟수를 미리 계산해놓는다.
 
3. 4부터 N까지 숫자에 대해 이전 값들을 이용해 최소 연산 횟수를 계산하여 dp[i]값을 업데이트한다.
 
3-1. i가 2와 3으로 모두 나누어 떨어진다면,  i에서 2를 나눈 값과, 3을 나눈 값, 1을 뺀 값의 최소 연산 횟수 중 가장 작은 값에서 1을 더한 값이 dp[i]이다.
 
3-2. i가 2로만 나누어 떨어진다면,  i에서 2를 나눈 값과 1을 뺀 값의 최소 연산 횟수 중 가장 작은 값에서 1을 더한 값이 dp[i]이다.
 
3-3. i가 3으로만 나누어 떨어진다면,  i에서 3를 나눈 값과 1을 뺀 값의 최소 연산 횟수 중 가장 작은 값에서 1을 더한 값이 dp[i]이다.
 
+ 1을 더하는 이유는 이전 값에서 다시 2를 곱하거나, 3을 곱하거나, 1을 더해줘야 하기 때문이다.
 
4. 반복문을 이용하여 위 과정처럼 Bottom-Up 방식으로 이전 dp[i]값을 통해 최종적으로 dp[N]값을 업데이트하고 출력한다.