[백준] 1643번 - 1로 만들기

야금야금 공부·2023년 3월 31일

DP 백준

백준

목록 보기

2/52

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

실버3

문제

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

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

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

입력

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

출력

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

문제 해결1

이코테의 DP 방식(상향식)을 적용

x = int(input())
d = [0] * (x + 1)

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

    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1)

print(d[x])

분석

1) 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 d를 초기화한다.

d[x]는 인덱스 x만큼의 수가 1이 될 때 까지의 최소 연산 횟수를 담는다.
크기는 입력값 x + 1

2) 2 부터 x 범위 까지 반복 : for i in range(2, x+1)
3) i에서 1을 빼는 연산(d[i]) : (i - 1)번째가 1이 되는 최소 연산(d[i-1]) + 1
4) i를 2로 나눌 수 있을 때, 1을 빼서 만든 최소 연산 횟수(d[i])와 2로 나눠 1이 된 횟수(d[i//2] + 1) 중 최소값을 선택한다.

if i % 2 == 0:
	d[i] = min(d[i], d[i//2] + 1)

5) i를 3으로 나눌 수 있을 때, 위의 4)를 반복한다.
6) 입력값 x가 1이 되는 최소 연산 횟수인 d[x]를 출력한다.

문제 해결2

하향식 적용

x = int(input())
dp = {1: 0}  # 1이 되는데 필요한 횟수는 0

def rec(n):
    if n in dp.keys():
        return dp[n]
    if (n % 3 == 0) and (n % 2 == 0):
        dp[n] = min(rec(n // 3) + 1, rec(n // 2) + 1)
    elif n % 3 == 0:
        dp[n] = min(rec(n // 3) + 1, rec(n - 1) + 1)
    elif n % 2 == 0:
        dp[n] = min(rec(n // 2) + 1, rec(n - 1) + 1)
    else:
        dp[n] = rec(n - 1) + 1
    return dp[n]

print(rec(x))