[백준,Python]1463번_1로 만들기(DP,Dynamic Programming)

백준 알고리즘(Dynamic Programming 문제)들 중 

*1463번_1로 만들기 문제*는 풀어 보면서 느끼는 것도 많고,

굉장히 중요한 문제라고 생각이되어 따로 정리해보는 시간을 가져보려 합니다.

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

 

문제를 쭉 보고 생각을 해보니 N이라는 정수를 입력받았을 때 

3가지 연산식을 이용해 N을 나타내는 데 최소값을 구하는 것이니까

min(3i+1, 2i+1,i)로 나타낼 수 있을 것라 생각했다.

 

그리고 최솟값이 되려면 3으로 나누고 1을 빼주는 것이 무조건 최솟값이므로 (같은 수N을 나타내려면 3i+1과 2i+1 중 당연히 3i+1의 i 값이 더 작을 것이기 때문) while문으로 1이 아닐 때 3으로 나누고 못나눌 경우 1을 뺴주고 나누고를 반복한 연산식의 수를 구하려고 생각하였다. 그래서 DP는 아니지만 이렇게 간단하게 모든 답이 맞는 코드를 구현하였다.

 

count = 0
N = int(input())
while N>1:
    if N%3==0:
        N=N/3
        count +=1
        continue
    else:
        N=N-1
        count +=1
        continue
print(count)

 

하지만, 당연히 DP문제를 DP로 풀지 않았기 때문에 '틀렸습니다'가 나타났다...

다시 정신을 차리고 동적 프로그래밍 방법을 찾아서 공부한 후 2가지 방법이 있는 것을 알 수 있었다.

 

첫 번째는 Top-Down식으로 큰 수를 작게 만들면서 반복(재귀)을 해주는 방식이다.

하지만, 재귀를 하게 되면 많은 메모리를 사용하게 되어, 메모리 초과가 되므로 Bottom-Up형식으로 코드를 구현하였다.

#세 가지 연산이 있다(Dynamic Programming)
#1.x가 3으로 나누어 떨어지면, 3으로 나눈다.
#2.X가 2로 나누어 떨어지면, 2로 나눈다.
#3.1을 뺀다.
#정수 한 개를 입력 받아 1로 만들고 연산을 사용한 횟수를 출력.
N = int(input())
arr = [0]*(N+1)
for i in range(2,N+1):
    arr[i] = arr[i-1]+1
    if i%2==0 and arr[i]>arr[i//2]+1:
        arr[i]=arr[i//2]+1
    if i%3==0 and arr[i]>arr[i//3]+1:
        arr[i]=arr[i//3]+1
print(arr[N])

 

-arr배열을 처음에 모두 0으로 초기화를 시킨 후 for문을 돌려 arr배열에 연산식을 사용한 수를 집어 넣었다.

-for 문에서 i는 N+1까지의 모든 정수들을 다 구하여 계산을 돌리고 arr배열에 넣었다.

-N+1까지 범위를 설정한 이유는, N=1일때 0번이고 N=2일때 1번으로 range를 2부터 start했기 때문에 그렇게 설정하였다.