[다이나믹 프로그래밍 / 동적계획법] 실전 문제 <2> 1로 만들기 / 이것이 취업을 위한 코딩테스트다 with 파이썬

1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

• X가 5로 나누어떨어지면, 5로 나눈다.
• X가 3으로 나누어떨어지면, 3으로 나눈다.
• X가 2로 나누어떨어지면, 2로 나눈다.
• X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.

26 - 1 = 25

25 / 5 = 5

5 / 5 = 1

 

입력 조건

• 첫째 줄에 정수 X가 주어진다. (1 ≤ X ≤ 30,000)

 

출력 조건

• 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

입력 예시

26

출력 예시

3

 

내 풀이

X = int(input())

d = [0] * 30001

d[2] = 1
d[3] = 1
d[4] = 2
d[5] = 1

for i in range(6, X+1):
    result = 987654321
    if i % 5 == 0 and (d[int(i/5)] + 1) < result:
        result = d[int(i/5)] + 1
    if i % 3 == 0 and (d[int(i/3)] + 1) < result:
        result = d[int(i/3)] + 1
    if i % 2 == 0 and (d[int(i/2)] + 1) < result:
        result = d[int(i/2)] + 1
    if (d[int(i-1)] + 1) < result:
        result = d[int(i-1)] + 1
    d[i] = result

print(d[X])

 

모범 코드

X = int(input())

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)

print(d[X])

 

출처

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년