[백준] 1463. 1로 만들기

 

📪 [1로 만들기]

 

1463번: 1로 만들기

 

---

 

 

📋 문제설명

정수 X에 사용할 수 있는 연산은 다음과 같은 조건을 만족해야 한다

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

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

 

 

 

 

👁‍🗨 입출력 데이터

[입력]

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

2

[출력]

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

1

 

 

 

 

🔑 문제풀이

최솟값을 구하는 문제이고, 가장 효율적인 순서가 %3,%2,-1의 순서이기에 자칫하면 '그리디' 유형의 문제라 파악할 수 있다. 허나 이는 잘못된 풀이인데 왜냐하면 N=10일 경우, 해당 풀이를 통한 답은 5이나 정답은 4이기 때문이다.

# 잘못된 풀이
n = int(input())
d = [0]*(n+1)

for i in range(2, n+1):					# %3, %2, -1 순이 최적의 해로 보이나 → 모든 경우에 성립 X.
    if i % 3 == 0:				        # 모든 상황을 고려하여 비교함 필요, "DP 풀이"!!
        d[i] = d[i//3] + 1
    elif i % 2 == 0:
        d[i] = d[i // 2] + 1
    else:
        d[i] = d[i-1] + 1

print(d)
print(d[n])

따라서 위처럼 최적의 방법으로 해를 구하고자하는 그리디 알고리즘으로 답을 도출해서는 안된다. 그렇다면 어떻게 풀어야 할까?

 

위 문제의 주어진 조건을 정리하면, D[i] = min(D[i/3]+1, D[i/2]+1, D[i-1]+1)이라는 수식으로 표현이 가능하다.

즉 점화식을 이용하여 문제를 작은 문제로 쪼개어 풀 수 있기에 이는 '다이나믹 프로그래밍' 유형의 문제이다. 

다이나믹 문제는 점화식을 구했다면 구현만 남는데 이때 구현의 경우 'top-down' 방식과 'bottom-up' 방식 두 가지 방식으로 구현이 가능하다. 먼저 top-down 방식을 이용하여 코드를 구현해보자. 구현한 코드는 아래와 같다.

# Top-Down(재귀 이용) : 재귀를 이용하게 되면 메모리 제한 때문에 메모리 초과가 되므로 Bottom-Up으로 푸는 것이 좋다.

import sys
sys.setrecursionlimit(1000000)  # 재귀 호출 제한 제거 (N<=10^6)


def go(n):
    if n == 1:
        return 0
    if d[n] > 0:
        return d[n]
    d[n] = go(n - 1) + 1	   # 배열에 미리 '최악의 경우(=1칸씩만 전진)'를 저장해 둠. 그리고 아래에서 비교를 통해 더 나은 값으로 교환
    if n % 2 == 0:
        temp = go(n // 2) + 1  # 나누기(/)로 하면 소수 나와서 오류 생김 (실수 X. 정수 O)
        if d[n] > temp:
            d[n] = temp
    if n % 3 == 0:
        temp = go(n // 3) + 1
        if d[n] > temp:
            d[n] = temp
    return d[n]


n = int(input())
d = [0] * (n + 1)				# DP 👉 "Memoization!"
print(go(n))

 

top-down 방식을 '재귀'를 통해 구현하였고, 파이참 에디터를 이용해 주어진 예들을 돌려보았을 때 모든 예의 답을 정확히 출력하는 것을 확인할 수 있었다. 허나 백준 사이트에 제출시 아래와 같이 메모리 초과 문제가 발생했다.

 

까닭은 일단 주어진 문제의 메모리 제한이 128 MB로 워낙 작은데다가, 재귀를 이용할 경우 파이썬에선 시간 및 메모리 소요가 너무 큰 탓이었다. 즉, top-down 방식을 통한 코드는 적합하지 않다는 것이다. 이를 해결하기 위해 두 번째 방식인 bottom-up 방식의 코드를 구현해보았는데 이 방식으로는 통과되는 것을 확인할 수 있었다. 해당 코드는 아래와 같다.

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

for i in range(2, n+1):     # for문을 통해 순차적으로 반복 진행!
    d[i] = d[i-1] + 1       # 순차적으로 채웠기 때문에 i-1부터 0까지 값들이 모두 d에 저장 有
    if i % 3 == 0:
        d[i] = min(d[i//3] + 1, d[i])           # 꼭 어떤 특정 조건이 최적의 최솟값이라는 보장 X. 따라서 min으로 비교해줌.
    if i % 2 == 0:                              # 마찬가지로 꼭 %3이 %2보다 최적이라는 보장 X. 따라서 elif가 아닌 if 처리.
        d[i] = min(d[i//2] + 1, d[i])    

print(d[n])

왜 파이썬을 이용하여 다이나믹 프로그래밍 문제를 풀 경우 왠만하면 'bottom-up' 방식으로 푸는 것이 권장되는지,, 그 이유를 뼈저리게 느낄 수 있었다..😭

 

 

 

 

---

 

 

🔔 풀이/개념정리

1. 재귀함수의 사용
   
2. 재귀함수의 제한 제거
   : sys.setrecursionlimit(1000000)  
3. 파이썬 & 다이나믹 문제 👉 bottom-up으로 풀어라!