[PART2] 8-1(DP): 1로 만들기

코뉴·2021년 2월 1일

이코테: 문제풀이

목록 보기

23/28

💥이코테 실전문제 뽀개기💥

💻 8-1 1로 만들기

난이도🖤🖤🖤🤍🤍🤍 | 풀이시간 20분 | 제한시간 1초 | 메모리제한 128MB

📌2021/02/01 작성 코드

import sys

x = int(sys.stdin.readline())
dptable = [0]*30001
for i in range(1, x+1):
    if i == 1:
        dptable[i] = 0
        continue

    if dptable[i] != 0:
        continue

    counts = []
    if i % 5 == 0:
        counts.append(dptable[i//5]+1)
    if i % 3 == 0:
        counts.append(dptable[i//3]+1)
    if i % 2 == 0:
        counts.append(dptable[i//2]+1)
    counts.append(dptable[i-1]+1)

    dptable[i] = min(counts)

print(dptable[x])

🔴 백준 1463 1로 만들기 문제와 유사

💭 아이디어

https://velog.io/@eastgloss0330/%EB%B0%B1%EC%A4%80-1463-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0

🤓 문제 해설

이 문제는 잘 알려진 DP 문제이다. 피보나치 수열 문제를 도식화했던 것처럼 문제를 풀기 전에 함수가 호출되는 과정을 그림으로 그려보면 이해하는 데 도움이 된다.

예를 들어 X=6일 때, 함수가 호출되는 과정을 그리면 다음과 같을 것이다. 확인해보면, 마찬가지로 f(2)와 같은 함수들이 동일하게 여러 번 호출되는 것을 알 수 있다. 이 문제에서 동일한 함수에서 구하는 값들은 동일해야 하므로 DP를 효과적으로 사용할 수 있다.

이제 문제에서 요구하는 내용을 점화식으로 표현해보자. 점화식 끝에 1을 더해주는 이유는 함수의 호출 횟수를 구해야 하기 때문이다.

ai = min(ai-1, ai/2, ai/3, ai/4)+1

이를 토대로 bottom-up DP로 코드를 작성한다. 실제 코드로 구현할 때는 1을 빼는 연산을 제외하고는 해당 수로 나누어 떨어질 때에 한해서만 점화식을 적용한다. 더불어 두 수 중에서 단순히 더 작은 수를 구하고자 할 때에는 파이썬에서의 min() 함수를 이용하면 간단하다.

🤓 답안 예시

# 정수 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])