[다이나믹 프로그래밍 알고리즘] 1로 만들기 - 파이썬(python)

1로 만들기

난이도 : 中下 풀이 시간 : 20분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

x = int(input())

dp_table = [0] * 30001

for i in range(2, x+1):
    dp_table[i] = dp_table[i-1] + 1

    if i % 2 == 0:
        dp_table[i] = min(dp_table[i], dp_table[i // 2] + 1)

    if i % 3 == 0:
        dp_table[i] = min(dp_table[i], dp_table[i // 3] + 1)

    if i % 5 == 0:
        dp_table[i] = min(dp_table[i], dp_table[i // 5] + 1)

print(dp_table[x])

---

예시

 

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

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
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)

print(d[x])

---

해설

 

다이나믹 프로그래밍 알고리즘은 이해하는 데 시간이 꽤 걸렸습니다.
우선 x에 입력을 받고, 시간을 최소화하기 위하여 작은 단계들의 계산값을 저장할 dp 테이블을 만들어줍니다.
그리고 for 반복문으로 2부터 x+1까지 반복해줍니다. (d[1]은 0이기 때문에 2부터 시작합니다.)
우선 2, 3, 5 아무것도 나누어지지 않는 경우에는 i의 인덱스를 1 줄여줍니다. (횟수는 +1)
2로 나누어 떨어지는 경우에는 i의 인덱스를 2 나누어줍니다. (횟수는 +1)
3로 나누어 떨어지는 경우에는 i의 인덱스를 3 나누어줍니다. (횟수는 +1)
5로 나누어 떨어지는 경우에는 i의 인덱스를 5 나누어줍니다. (횟수는 +1)
15같은 수는 3으로 5번 나누는 것보다 5로 3번 나누는 것이 효율적이므로, 5로 나누어 떨어질 때의 경우를 가장 마지막에 배치하였습니다.
각각 조건문 속에서는 d[i // 2], d[i // 3], d[i // 5]는 이미 계산해서 dp 테이블에 담긴 수이기 때문에 시간을 효율적으로 사용할 수 있습니다.
마지막으로 입력받은 x의 인덱스에 해당하는 d[x]를 출력해주면 됩니다.