[백준 1463번] 1로 만들기

n = int(input())

dp = [0]*3000003

for i in range(1,n+1):
    
    if dp[i+1] == 0:
        dp[i+1] = dp[i] + 1
    else:
        dp[i+1] = min(dp[i+1], dp[i]+1)
    
    if dp[i*2] == 0:
        dp[i*2] = dp[i] + 1
    else:
        dp[i*2] = min(dp[i*2], dp[i]+1)

    if dp[i*3] == 0:
        dp[i*3] = dp[i] + 1
    else:
        dp[i*3] = min(dp[i*3],dp[i]+1)

print(dp[n])

이번 문제는 입력받은 N을 '2로 나누기', '3으로 나누기', '1 빼기' 이 세가지 연산을 가지고 1을 만들 수 있는 최소 연산횟수를 구하는 문제였다.

 

처음에는 입력받은 N 값에서부터 시작하여 1로 만드려고 했는데, 이 문제는 Greedy하게 풀 수 있는 문제가 아니었음을 깨닫고 DP 알고리즘 중에서도 1에서 반복문을 사용하여 차근차근 값을 구하는 방식(Bottom-Up)으로 풀이하였다 !

 

본인이 떠올린 풀이는 다음과 같다.

 

1. 최소 연산 횟수를 저장할 수 있는 별도의 DP 리스트를 생성 및 초기화한다.(dp)

2. 먼저 1부터 시작하는데, 이때는 별도의 연산이 필요하지 않으므로 0이다.

3. n의 값(여태까지의 최소 연산 횟수)을 기준으로 DP리스트의 n+1, n*2, n*3 번째 값을 업데이트한다.(0인 경우에는 업데이트, 0이 아닌 경우에는 '현재 n의 값 +1'과 'n+1 / n*2 / n*3 의 값' 중 최소 값으로 업데이트)

 

이 방식으로 풀었을 때 바로 성공할 수 있었지만 DP 리스트의 크기를 3000003 으로 선언 및 초기화 시켜주어야 하고, 쓸데없는 연산이 많이 들어간다는 단점이 있었다.

 

따라서 다른 풀이를 참고해본 결과, DP리스트의 크기를 최소화하면서 깔끔하게 풀 수 있는 모범답안은 다음과 같다.

n = int(input())

dp = [0]*(n+1)

for i in range(2,n+1):
    # 2나 3으로 나누어 떨어지지 않은 경우 무조건 1을 빼야 하기 때문
    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)

print(dp[n])

 

메모리/속도 측면에서 2번째 풀이가 훨씬 효율적인 모습

N에서부터 답을 구하는 것이 아니라, 1에서부터 거꾸로 풀이하는 Bottom-Up 방식으로 DP 알고리즘을 활용하여 풀 수 있었던 좋은 문제였다 :)