Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
다이나믹 프로그래밍
최적해를 구하기에 시간이나 메모리 공간이 많이 필요한 문제들은 컴퓨터로 해결하기 어렵다.
→ 효율적인 알고리즘 필요
다이나믹 프로그래밍
종류
- 탑다운 방식: 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식 = 재귀 함수
- 보텀업 방식: 작은 문제부터 답 도출 = 반복문
적용 방식
- 완전 탐색 알고리즘으로 접근했을 때 시간이 오래 걸리는 경우 의심
- 작은 문제에서 나온 답을 이후 큰 문제에서도 사용할 경우 적용
- 재귀함수보다 보텀업 방식 권장 (스택 크기 제한때문..)
문제: 1로 만들기
문제
정수 x가 주어질 때 x로 사용할 수 있는 연산은 다음 4가지이다.
- x가 5로 나누어 떨어지면 5로 나눈다.
- x가 3으로 나누어 떨어지면 3으로 나눈다.
- x가 2로 나누어 떨어지면 2로 나눈다.
- x에서 1을 뺀다.
이 4가지 연산을 이용해 1을 만들 때, 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
- 첫째 줄: 정수 x
출력
- 연산 횟수의 최솟값
코드
x = int(input())
d = [0] * 100
for i in range(2, x+1):
d[i] = d[i - 1] + 1
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])
