백준 파이썬 1463번 1로 만들기 (Today I Learn 2024.12.01)

백준 파이썬 공부 2024.12.01
1463번 1로 만들기

1. 문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 
연산을 사용하는 횟수의 최솟값을 출력하시오.

2. 입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

3. 출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

4. 코드 풀이 과정
n을 3으로 나눌 수 있다면,
n을 2로 나눌 수 있다면,
n을 -1 한다면,
의 순서로 풀이 시 최솟값이 출력되지 않는다.

10의 경우 
10 >> 5 >> 4 >> 2 >> 1
10 >> 9 >> 3 >> 1

그래서 6의 배수로 만들고 나누는 방식을 생각해 봤으나 틀림

>>>코드1. 틀림

def cal(n, count):
    if n == 1:
        return count
    elif n%3 == 0:
        return cal(n//3, count+1)
    elif n%2 == 0:
        return cal(n//2, count+1)
    else:
        return cal(n-1, count+1)

n = int(input())
result = 10**6
for i in range(6):
    m = n-i
    count = i
    result = min(cal(m, count), result)

print(result)

DP(다이나믹 프로그래밍)를 이용하는 방식을 따라야 한다

2부터 n 까지 각각의 수까지 가는 최소횟수를 계산하고,
이전의 수까지 가는 최소 횟수를 이용하여 다음 수의 최소 연산 횟수를 계산

1. n 까지의 기본 최소 연산 횟수 == n-1까지의 최소 연산 횟수 +1
2. n이 2로 나누어 진다면, n//2 까지의 최소 연산횟수 +1 과 기본값 중 작은 값
3. n이 3로 나누어 진다면, n//3 까지의 최소 연산횟수 +1 과 기본값 중 작은 값

>>> 코드2 DP 사용

n = int(input())
dp = [0] * 1000001

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1 # 일단 기본 값을 dp[i-1]의 횟수 +1한 방식으로 저장
    
    if i % 2 == 0: # 2로 나누어 떨어지는 경우, 최소값 갱신
        dp[i] = min(dp[i], dp[i//2] + 1) # i//2까지 가는 최소값 + 1
    
    if i % 3 == 0 :# 3으로 나누어 떨어지는 경우, 최소값 갱신
        dp[i] = min(dp[i], dp[i//3] + 1) # i//3까지 가는 최소값 + 1

print(dp[n])

5. 문제링크
https://www.acmicpc.net/problem/1463