이코테-chapter8: 1로 만들기

정리 내용

문제 설명

• 난이도: 중
• 시간 제한: 1초
• 메모리 제한: 128mb
• 정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지이다.
  1) x가 5로 나누어떨어지면, 5로 나눈다.
  2) x가 3으로 나누어 떨어지면, 3으로 나눈다.
  3) x가 2로 나누어 떨어지면, 2로 나눈다.
  4) x에서 1을 뺀다.
• 정수 x가 주어졌을 때, 연산을 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하라.

문제 풀이

• 다이나믹 프로그래밍 알고리즘으로 문제를 해결한다.
• 점화식 끝에 1을더해주는 이유는 호출 횟수를 구해야 하기 때문이다.

소스 코드

x = int(input())

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

# 다이나믹 프로그래밍 진행 (bottom-up)
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//2]+1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i%5 == 0:
        d[i] = min(d[i], d[i//5] + 1)

print(d[x])

출처 & 깃허브

이것이 취업을 위한 코딩 테스트다 with python

github