[다이나믹 프로그래밍] 1로 만들기 (실전문제, 이것이 코딩테스트다 with 파이썬)

다이나믹 프로그래밍(Dynamic Programming) (= 동적 계획법)

메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

 

문제

 

해설

최소값을 구하기 위해서는 다 빼보고 나눠봐야 함!!!

근데 비효율을 방지하기 위해서 다이나믹 프로그래밍으로 구현

 

문제에서 요구하는 내용을 점화식으로 표현하면 위와 같다

이전까지의 최소값을 구한 후에 그 함수를 호출하는 횟수 +1을 하면 된다

 

풀이

# 정수 x를 입력받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001

# 다이나믹 프로그래밍 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i]. d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

 

해석

변수 : x 정수, d 보텀업에서 DP테이블, i 현재의 수

 

1. 정수 x 입력받기

2. DP테이블 초기화 : [0] * 30001

-------- 다이나믹 프로그래밍 : DP 테이블에서의 최소값 --------

ㄴ 현재의 수 i

ㄴ 2 ~ x 까지의 반복문 수행

3. 각 경우에 따른 최소값으로 업데이트

ㄴ -1에 대한 연산 : d[i] = d[i - 1] + 1

ㄴ 2 나누기에 대한 연산 : min(기존 d[i], d[i // 2] + 1)     # 2 나누기 연산 수행하므로 +1

ㄴ 3 나누기에 대한 연산 : min(기존 d[i], d[i // 3] + 1)     # 3 나누기 연산 수행하므로 +1

ㄴ 5 나누기에 대한 연산 : min(기존 d[i], d[i // 5] + 1)     # 5 나누기 연산 수행하므로 +1

---------------------------------------------------------------------------------

4. 최소값으로 자동 업데이트되어 d[x] 출력