[Python] 1로 만들기 - DP

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

1463번: 1로 만들기

 

생각과정

- n이 1일 경우 0, 2일 경우 1, 3일 경우 1번의 연산으로 1을 만들 수 있다.

- 일차원 배열을 만들어 인덱스값에 대한 최소 연산 횟수를 저장한다. 

- 4부터 n까지 순회하면서 최솟값을 구한다. (Bottom-Up 방식)

- 먼저 3이나 2로 나누어 떨어지는지 확인한다. 나누어 떨어진다면, n/3 또는 n/2의 값에서 1을 더한 값을 배열에 저장한다. 앞에서 n/3의 최솟값을 구해 놓았으니 1을 더하기만 하면 된다.

- 1을 빼는 연산은 2나 3으로 나누어 떨어지지 않을 때 수행하거나, 앞의 두 연산보다 더 효율적일 때 수행한다. 1을 빼는 연산은 이전 값(n-1)에서 1을 더한 것을 저장한다.

 

구현

def solution(x):
    m = [0]*(x+1)
    m[1] = 0
    if x>=2:
        m[2] = 1
    if x>=3:
        m[3] = 1

    for i in range(4, x+1):
        num = x+1
        if i%3 == 0:
            if int(i/3)%3 == 0:
                m[i] = m[int(i/3)]+1
            else:
                m[i] = m[int(i / 3)] + 1
            num = m[int(i/3)]+1
        if i%2 == 0:
            if num > m[int(i/2)]+1:
                m[i] = m[int(i/2)]+1
                num = m[int(i / 2)] + 1

        if m[i] > m[i-1]+1:
            m[i] = m[i-1]+1
        if num == x+1:
            m[i] = m[i-1]+1

    answer = m[x]
    return answer


n = int(input())
print(solution(n))

 

결과

dp 문제는 코드는 간단한데,,