[백준/DP] 1463: 1로 만들기 - 파이썬

문제

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

1463번: 1로 만들기

 

풀이

다이나믹 프로그래밍으로 푸는 대표적 문제

 

문제에서 구하고자 하는 값은 

정수 X가 주어졌을 때

• 3으로 나누어 떨어지면 3으로 나누고
• 2로 나누어 떨어지면 2로 나누고
• 그 이외는 1을 뺀다.

규칙에 따라 연산 횟수의 최솟값을 구하는 문제다.

 

처음에 그리디 문제인줄 알고 n//3, n//2 , n-1 순서대로 구하였지만 

이렇게 풀면 최솟값을 구할 수 없다.

 

10을 입력해 위와같이 풀면

10 -> 5 -> 4 -> 2 -> 1 (5번)

 

여기서 10에 n-1 먼저 계산하면

10 -> 9 -> 3 -> 1 (4번) 으로 최소값을 구할 수 있다.

 

최솟값을 기록하는 배열 d를 먼저 선언하고 d의 인덱스는 숫자 n이며 d[n] = n을 1로 만드는 최소 연산의 횟수를 지정하였다.

즉, d[5]는 숫자5를 1로 만드는데 필요한 최소 연산 수, d[9]는 숫자 9를 1로 만드는데 필요한 최소 연산 횟수를 저장하였다.

 

그렇다면 d[n]을 구하려면 n이 1일때부터 숫자 n까지 각 n을 1로 만드는 최소 연산 횟수를 구하면 된다.

d[1]부터 d[7]까지 구하는 과정을 생각해보자

 

d[1]은 이미 숫자 1이기 때문에 연산이 필요하지 않으므로 d[1] = 0

d[2]는 숫자2를 2로 나누면 값은 1이므로 d[2] = 1

d[3]은 숫자3을 3으로 나누면 값은 1이므로 d[3] =1

d[4]는 숫자4를 2로 나누면 2, 2에서 2로 나누면 1이므로 d[4] = 2

d[5]는 숫자5가 2, 3으로 나누어지지 않으므로 -1하여 숫자 4로 만들고 4/2 = 2, 2/2 = 1 이 되어 d[5] = 3

d[6]은 숫자6이 2,3 으로 나누어지므로 6/3 = 2, 2/2 = 1 또는 6/2 = 3, 3/3 = 1 이므로 d[6] = 2

d[7]은 숫자7이 2,3으로 나누어지지 않으므로 -1하여 6으로 만들었다. 6/3 = 2, 2/2 = 1 또는 6/2 = 3, 3/1 이므로 

d[7] =3

 

여기서 dp를 사용하는 방법이 보일 것이다.

n이 7일때 n에서 1을 빼면 6이다. 

d[6]은 2, (6이 1이 되기 위해 2번 연산을 한다는 뜻)

여기서 d[7] = 7에서 1을 빼는 연산횟수 + 6에서 1이 되는 연산횟수 와 같음을 알 수 있다.

이를 식으로 나타내면 d[7] = 1 + d[6] 이며

점화식으로 나타내면 다음과 같다.

d[n] = min( d[n//3] + 1, d[n//2] + 1, d[n-1] + 1 ) 

import sys
input = sys.stdin.readline
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])

d는 앞서 설명한 n이 되기 위한 연산 최솟값을 저장하는 배열이다.

 

위의 풀이는 리스트를 사용하였는데 파이썬에서 리스트는 시간복잡도가 좋지 않은 자료형이다.

아래 풀이는 딕셔너리를 자료형을 이용해 재귀로 푼 방법이다. (해당 블로그 참조)

import sys
input = sys.stdin.readline

N = int(input())
dist = {1: 0, 2: 1}

def dp(n):
    if n in dist:
        return dist[n]

    cnt = 1 + min(dp(n // 3) + n % 3, dp(n // 2) + n % 2)
    dist[n] = cnt

    return cnt

print(dp(N))

위의 리스트를 이용한 방법보다 시간복잡도가 효율적이다.