Python 83 - 다이나믹 프로그래밍 실전문제1 ("1로 만들기")

난이도 ●◐○    l    풀이 시간 20분    l    시간 제한 1초    l    메모리 제한 128MB    l

문제 

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

출력조건

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

문제 해설

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

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

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

따라서 이 점화식을 토대로 보텀업 다이나믹 프로그래밍으로 소스코드를 작성해보자. 실제 코드로 구현할 때는 1을 빼는 연상를 제외하고는 해당 수로 나누어 떨어질 떄에 한해서만 점화식을 적용할 수 있다. 더불어 두 수 중에서 단순히 더 작은 수를 구하고자 할 떄는 파이썬에서의 min()함수를 이용하면 간단하다.

답안예시

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

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

# 다이나믹 프로그래밍(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])

 

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding