정수 X가 주어진다.
정수 X에 다음 4가지 연산을 사용할 수 있다.
- X가 5로 나누어떨어지면, 5로 나눈다
- X가 3로 나누어떨어지면, 3으로 나눈다
- X가 2로 나누어떨어지면, 2로 나눈다
- X에서 1을 뺀다
정수 X가 주어졌을 때, 연산 4개를 적절히 사용하여 1을 만든다. 이때 연산을 사용하는 횟수의 최솟값을 구하라.
a. 예를 들면
정수 26이면, 산을 사용하는 횟수의 최솟값이 3이다.
- 26 - 1 = 25 (4)
- 25 / 5 = 5 (1)
- 5 / 5 = 1 (1)
b. 입력 조건
- 첫째 줄에 정수 X가 주어진다.
- 1 <= X <= 30,000
c. 출력 조건
- 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
d. 테스트 케이스
- 입력 예시
- 26
- 출력 예시
- 3
코드
# 정수 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])
'문제풀이 > DP' 카테고리의 다른 글
[파이썬] [DP] 개념 정리 (0) | 2022.01.24 |
---|---|
[파이썬] [DP] 백준 18353 병사 배치하기 (0) | 2022.01.24 |
[파이썬] [DP] 금광 (0) | 2022.01.24 |
[파이썬] [DP] 효율적인 화폐 구성 (0) | 2022.01.24 |
[파이썬] [DP] 개미전사 (0) | 2022.01.24 |