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

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

1463번: 1로 만들기

문제

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

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

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

입력

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

출력

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

---

풀이

처음에는 1이 될 때 가지 while문을 돌며 연산을 수행하도록 코드를 짜보았다

X = int(input())
cnt = 0

while X != 1:
    if X % 3 == 0:
        X = X // 3
        cnt += 1
    if X % 2 == 0:
        X = X // 2
        cnt += 1
    else:
        X -= 1
        cnt += 1
    print(X)
print(cnt)

이렇게 코드를 짜면 예제의 10만 입력해도

10 -> 5 -> 4 -> 3 -> 1 로 4번의 연산과정을 거치게 된다.

 

DP로 코드를 풀어야 했는데 그 과정을 이해하는게 너무 어려웠다

 

일단 입력값이 1 인 경우 이미 1이기 때문에 연산과정은 0이다

2인 경우 1을 빼는 방법과 2를 나누는 과정을 통해 1을 만들고 연산과정은 1이다

3인 경우 3으로 나누어 연산과정은 1이 된다

4인 경우 2로 난거나 1을 뺀다(+1) 그리고 2나 3은 각 각 연산과정이 1개 이므로 4인 경우 연산과정은 2가 된다

5인 경우 1을 빼는 연산과정을 거치고 (+1) 4는 이미 2번의 연산 과정을 가지고 있기 때문에 연산과정은 3이 된다

6인 경우 나누기 연산과정을 거치고(+1) 2 또는 3은 1번의 연산과정을 가지고 있으므로 연산과정은 2가 된다

.

.

.

이런 식으로 앞의 연산 과정이 가진 수를 토대로 값을 구해나가야 한다!

 

2나 3으로 나눠지지 않는 수는 1을 빼서 앞의 수로 만들어 준 후 연산과정을 계산해야하므로

arr[i - 1] + 1과정을 매번 거친다

만약 나눠질 경우 나눠진 숫자로 만든 후 연산과정을 계산하므로 3혹은 2로 나눠주었다!

python 코드

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

for i in range(2, x+1):
    arr[i] = arr[i - 1] + 1

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

    print(arr)
print(arr[x])