[backjoon] 1463 1로 만들기 (python)

문제 1463번: 1로 만들기

Dynamic Programming

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

예제 입력

10

예제 출력

3

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

---

문제풀이

이 문제는, 앞에서 구한 결과값을 저장하였다가 후에 사용하는 문제이다.

• dp = [0] * (n+1) ➡ 계산된 값을 저장하기 때문에
• dp[i] = dp[i-1] + 1에서 [i-1]을 빼고 시작하는 이유는 다음에 계산할 나누기가 1을 뺀 값보다 작거나 크기에 따라 교체되기 때문이다.
  즉, min()함수를 통해 비교를 할 예정이기 때문이다.
• if문 ➡ 여기서 if elif else를 사용하면 안된다. if만 이용해야 세 연산을 다 거칠 수 있다.
• dp[i//2]+1 ➡ 1을 더하는 것은 d는 결과가 아닌 계산한 횟수를 저장하는 것 이기 때문
• dp[i] ➡ d[i]에는 더하지 않는 이유는 이미 1을 뺄 때 1을 더해준 이력이 있기 때문

---

전체코드

import sys
input = sys.stdin.readline

n = int(input())

# 계산된 값을 저장
dp = [0] * (n+1)

for i in range(2, n+1):
	# 1을 빼고 시작하는 이유는 
    # 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 
    # 어차피 교체되기 때문에
    dp[i] = dp[i-1] + 1
    # 여기서 if elif else를 사용하면 안된다. 
    # if만 이용해야 세 연산을 다 거칠 수 있다
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[n])

출처 [파이썬] 백준 - 1463: 1로 만들기 (매우 자세한 해설 포함)