[백준 / Python] 1로 만들기

1로 만들기

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

---

나의 풀이

전형적인 dp 문제

n = 10일 경우의 점화식을 완성하지 못함

import sys
input = sys.stdin.readline
n = int(input())
print(n)
dp = [0] * (10**6 + 1)
dp[2] = 1
dp[3] = 1
print(dp)
for i in range(4,n+1): # 5
    # 4 => 4
    print(i)
    if i % 3 == 0:
        dp[i] = dp[i // 3]  + 1
    elif i % 2 == 0:
        dp[i] = dp[i // 2]  + 1
        print(dp)
    else:
        dp[i] = dp[i-1]+ 1
        print(dp[i], i)

리팩토링

• dp테이블은 n의 갯수만
• 최솟값을 구해야 하므로 min() 을 사용

import sys
input = sys.stdin.readline
n = int(input())

dp = [0] * (n + 1)
#n + 1이라고 한 이유는, 1번째 수는 사실 d[1]이 아니고 d[2]이기 때문에,
# 계산하기 편하게 d[1]을 1번째 인 것 처럼 만들어준다.

for i in range(2, n + 1):
## 여기서 왜 if 1빼는 방법, 2 나누기, 3 나누기 동등하게 하지 않고 처음에 1을 빼고 시작하는지 의아해 할 수 있다.
## 1을 빼고 시작하는 이유는 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문이다.
## 즉 셋 다 시도하는 방법이 맞다.

## 여기서 if elif else를 사용하면 안된다. if만 이용해야 세 연산을 다 거칠 수 있다, 가끔 if continue, else continue를 쓰는 분도 계신데, 난 이게 편한듯.

#d[i] = d[i - 1] + 1을 먼저 계산하는 이유는 i - 1의 경우를 
#기본값으로 설정하고, 그 후에 i / 3과 i / 2의 경우를 고려하여 필요하다면 값을 업데이트하기 위함
 dp[i] = dp[i - 1] + 1
 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)
     ## 1을 더하는 것은 d는 결과가 아닌 계산한 횟수를 저장하는 것 이기 때문이다. d[i]에는 더하지 않는 이유는 이미 1을 뺄 때 1을 더해준 이력이 있기 때문이다.

print(dp[n])