[DP] 백준 1463: 1로 만들기

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

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

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

---

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

---

 

문제 풀이에 들어가기 앞서 한가지 짚고 넘어가야 할 부분이 있다.

dp는 어떤 경우에 사용해야 할까? 난 작은 문제가 중복되어 나타날 때 dp를 고려해보는 편이다.

 

피보나치 수열을 예로 들어보자.

1, 1, 2, 3, 5, 8, 13 ... 이와 같은 방식으로 이어지는 수열이 피보나치 수열이다.

1번째와 2번째를 제외한 n번째 항은 n-1번째 항과 n-2번째 항의 합으로 구성되어 있다.

이 수열을 코드로 구현하면 아래와 같다.

def fibo(n):
    if n == 2 or n == 1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

for i in range(1, 11): # 수열의 10번째까지 표시
    print(fibo(i))

10번째 값까지 보여주는데는 시간이 많이 걸리지 않는다. 그러나 100번째라면? 1000번째라면? 아마 어마무시한 횟수의 재귀를 반복해서 돌아야 할 것이다.

이를 해결하기 위해선 어떻게 해야 할까?

답은 간단하다. 각 단계의 fibo 값을 어딘가에 저장해두고, 다음 fibo값을 계산할 때 저장된 값을 불러오는 것이다.

즉 fibo(100) 이라는 값을 구하기 위해 재귀를 겁나 돌리는 것이 아닌 fibo(99)와 fibo(98)을 사용하는 것. 간단한 개념이라고 생각한다.

 

그럼 문제로 돌아가보자.

주어진 숫자를 1로 만들기 위한 최소 연산 횟수를 구해야 한다.

어떻게 해야 할까?

작은 숫자부터, 즉 2부터 시작해(1은 이미 1이므로 연산할 필요가 없다.) 목표가 되는 수인 N까지 역으로 거슬러 올라가 보면 좋을 것 같다.

 

숫자 2를 예로 들면, 2를 1로 만들기 위한 최소 연산 횟수는 1이다. 이는 변하지 않으므로 2의 위치에 1을 저장해둘 수 있다.

그 다음은 3. 3을 만들기 위한 연산 방법엔 2가지가 있다. 첫째는 2에서 1을 더하는 것, 둘째는 1에서 3을 곱하는 것.

이 때 연산 횟수를 최소로 만들어 줘야 하기 때문에 (2의 위치에 저장된 값 + 연산 1회 추가) vs (1의 위치에 저장된 값 + 연산 1회 추가)를 비교하여 더 적은 값을 3의 위치에 저장해주면 된다.

 

위와 같은 로직을 활용해 코드를 짜면 다음과 같다.

N = int(input())
arr = [0] * (N + 1) # 인덱스 고려, 인덱스 값과 수가 일치
for i in range(2, N+1): # 0과 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[N])

비슷한 문제를 풀어봤다면 쉽게 쉽게 풀 수 있는 문제이나, 처음 본다면 당황할수도 있는 문제.