1. 문제 설명
2. 문제 조건
3. 문제 해결 아이디어
- 피보나치 수열 문제를 도식화한 것처럼 함수가 호출되는 과정을 그림으로 그리면 이와같다.
- 최적 부분 구조와 중복되는 부분 문제를 만족
- 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해 점화식을 적용할 수 있다.
4. 답안
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])
- x가 30000만까지 들어올 수 있으므로 DP테이블은 30001까지 초기화한다.
- 4가지중 가장 작은 수를 찾아서 더할 것 이므로 매번 min함수로 호출하여 바꾼다.
#출력
26
3
'CodingTest > 다이나믹 프로그래밍' 카테고리의 다른 글
병사 배치하기 (0) | 2022.07.14 |
---|---|
금광 (0) | 2022.07.14 |
효율적인 화폐 구성 (0) | 2022.07.14 |
개미 전사 (0) | 2022.07.14 |
다이나믹 프로그래밍 개요 (피보나치 수열) (0) | 2022.07.13 |