[백준] BOJ1463, 1로 만들기

---

서론

 지난 코딩 포스팅에서는 백준 2566을 풀었다. 이번 포스팅에서는 다이나믹 프로그래밍(DP)을 이용한 1로 만들기를 풀어보고자 한다. 난이도는 백준 실버3에 해당한다. 풀이 과정에 대해서 설명을 하고 하단에는 BOJ 1463 코드를 첨부하겠다. 다이나믹 프로그래밍에 대한 포스팅을 보려면 아래 포스팅으로 가면 된다.

다이나믹 프로그래밍 DP 알고리즘 파이썬 코딩테스트 (11)

 

---

백준1463, 1로 만들기 풀이 과정

비슷한 문제로는 피보나치 문제가 있다. 피보나치는 단순 재귀로도 구현 가능하다. 하지만 재귀로만 풀게 된다면 시간 제약에 걸릴 것이다. 피보나치는 원하는 인덱스가 커질수록 기하급수적으로 계산이 늘어나면서 이전 연산은 그대로 사용하는 경향이 있다. 이전 값을 안다면 해당 계산 과정은 생략할 수 있는 것이다. 이 문제 역시 3에서 1로 만들거나 4에서 1로 만들기 123에서 1로 만들기 등 단 하나의 항만 고려하면 숫자가 커질수록 까마득하다. 그러나 이전 항에서 계산한 걸 이용한다면 그 과정을 확연히 줄일 수 있다. 간단하게 풀이 하는 과정을 설명하면 1) n에서 1로 만드는 과정을 계산하는데, 이는 2)  n//3, n//2, n-1 가 1로 만드는 과정에 1을 더한 값이 된다. 역으로 n//3에서 3을 곱한 것이(=하나의 계산 과정이 추가 되면) n임을 상기하면 되지 않을까 싶다. 3) 결론적으로 n//3, n//2, n-1에서 1로 가는 최소의 수 중 가장 작은 값에서 1을 더한 값이 n에서 1로 가는 최소한의 수라고 볼 수 있겠다.

 

---

BOJ 1463 코드

def min_operations_to_one(n):
    if n <1 :
        return 0
    dp = [0] * (n + 1)
    if n >=2:
        dp[2] = 1
    for i in range(3,n+1):
        tmp1, tmp2 = float('inf'), float('inf')
        if i%2 == 0:
            tmp1 = dp[i//2]
        if i%3 == 0:
            tmp2 = dp[i//3] 
        dp[i] = min(tmp1,tmp2,dp[i-1]) + 1
    return dp[n]
n = int(input())
print(min_operations_to_one(n))

내가 구현한건 다음과 같다. 1) dp라는 배열에다가 n까지 가는 수를 넣었다. 2)그리고 3부터 n+1까지 배열을 돌면서 i%2가 0일때와 i%3이 일 때, 각각 d[i//2], d[i//3]을 불러오고 그리고 d[n-1](얘는 항상 존재하기에) 이 세 값을 비교한 후 가장 작은값에다가 +1을 더해 d[n]에 넣었다. 그리고 이 값이 존재하지 않을때를 대비해 비교하기 전에 tmp1, tmp2를 무한대로 설정해놓았다.(다른 사람의 코드를 보고 알게 된 사실은 굳이 tmp1,tmp2로 리셋할 필요 없이 그냥 배열에다가 값을 넣으면 된다. tmp=[] 이렇게 하고 tmp.append(tmp1) 이런식으로하고 dp[n] = min(tmp)+1 이렇게 말이다.