[백준 / Python] 1463번 1로 만들기

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

 

[문제해석]

N을 입력하여 그 수가 위의 조건에 따라 1로 만드는 최소한의 횟수를 찾는 문제이다.

​

 

---

[코드]

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

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

print(d[n])

 

 

---

[문제 풀이]

1. n을 입력받는다.
2. n+1 개수만큼의 0으로 된 리스트를 생성하고, 리스트 시작을 0번째가 아닌 첫번째로 시작하기 위해 n+1개로 설정한다.
3. 입력된 값이 1이라면 어차피 계산횟수가 0이고, 그대로 출력하면 되므로 반복문을 2부터 시작한다.
4. 2부터 거슬러 올라가면서 n번째 원소까지 반복문을 돌린다.
5. d 리스트는 계산 횟수를 저장하는 리스트로, 1을 더하는 건 d[i] = d[i-1]+1로, 원소에 1을 더하는 것으로 생각할 수 있다.
6. 3또는 2로 나누어 떨어지는 경우, i를 3또는 2로 나눈 몫에 해당하는 원소에 계산횟수 1을 한번 더 더한 값과 원래 i번째 자리에 있던 원소를 비교해 작은 값을 d[i]에 갱신한다.
7. d[i//3] or d[i//2]를 하는 이유는, 그 값이 3또는 2로 나누어 떨어진다는 것은 그 숫자에 3또는 2를 한번 더 곱하면 계산이 완료됨을 의미하고, d[i//3] + 1 or d[i//2] + 1가 의미하는 것은 예를 들어 8이면 d[4]에 4까지 계산되는 최소 횟수가 저장되어 있을 것이고 여기에 2를 한번 더 곱하면 계산이 완료되는데 즉, 계산횟수를 1회 더하면 계산이 완료된 것이다. 이 계산횟수와 원래 d[8]에 저장돼있던 계산 횟수를 비교해 더 작은 수를 d[8]에 갱신하는 것이다.
8. 그렇게 최종 d[n]에 해당하는 계산횟수를 출력한다.

​

참고자료 : https://jae04099.tistory.com/199

 

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