1로 만들기
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:
# 1로 뺀경우랑 2로 나누어지는 경우 둘이 비교해서 작은거
d[i] = min(d[i], d[i // 2] + 1)
# 3으로 나누어 지는 경우
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])
이런 비슷한 문제를 그리디에서 푼것같아서 찾아보니 1이 될때까지 라는 비슷한 문제가 있었다.
그렇다면 다이나믹 프로그래밍으로 푼 문제와 그리디로 푼 문제와 차이점이 뭔지 찾아보니
그리디의 경우 무조건 나누어지는 값으로 나누고 그 값이 최적의 값을 보장해주는 문제여야 한다.
다이나믹의 경우 무조건 나누기보다는 모든 경우를 계산해 가작 최적의 값을 찾는것이다.
예를들어 16일 경우
16 8 4 2 1 (2로 나눠어 떨어지는 경우)
16 15 3 1 (1을 빼고 5로 나누는 경우)
밑에 방법이 더 최적의 값을 보장해준다.
그리디로 풀게되면 최적의 값의 예외가 생긴것이다.
다이나믹 프로그래밍을 살펴보자.
26을 입력하면
1. 2 4 12 13 26
2. 5 25 26
현재 이렇게 상향식 방법으로 밑에서부터 26이 되는 값을 찾는것이다.
그렇기 때문에 모든 경우를 고려해야한다.
d[i] = d[i - 1] + 1
# 2로 나누어지는 경우
if i % 2 == 0:
# 1로 뺀경우랑 2로 나누어지는 경우 둘이 비교해서 작은거
d[i] = min(d[i], d[i // 2] + 1)
# 3으로 나누어 지는 경우
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)
따라서 1을 빼는 경우 (2로 나눠진다면) 2로 나누는경우 (3으로 나눠진다면) 3로 나누는 경우를 모두 따져 min을 통해 최적의 값을 찾는다.
개미 전사
n = int(input())
data = list(map(int, input().split()))
d = [0] * 100
d[0] = data[0]
d[1] = max(data[1], data[0])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + data[i])
print(d[n - 1])
바닥 공사
n = int(input())
dp = [0] * 1001
# 2*1 한개
dp[1] = 1
# 2*2 1*2 2개 2*1 2개 -> 3개
dp[2] = 3
for i in range(3, n + 1):
# dp[i-2] -> 2*2 만들 수 있는 경우 2개 (2*2 / 1*2 2개) 따라서 2 곱함
dp[i] = dp[i - 1] + dp[i - 2] * 2
print(dp[n])
효율적인 화폐 구성
n, m = map(int, input().split())
data = [int(input()) for _ in range(n)]
# 모두 구할 수 없다고 기정
dp = [10001] * (m + 1)
dp[0] = 0
for i in range(n):
# 거스름돈 부터 M+1까지 -> 거스름돈 이하는 어차피 구할 수 없음
for j in range(data[i], m + 1):
# 현재 돈에서 - 거스름돈이 존재하는 값이면
if dp[j - data[i]] != 10001:
# 작은거 선택
dp[j] = min(dp[j], dp[j - data[i]] + 1)
if dp[m] == 10001:
print(-1)
else:
print(dp[m])
어렵지만 거의 비슷한 풀이 방식을 가진다.
점화식을 구하는게 포인트인 것 같고
연속해서 많이 풀어보면 익숙해질 듯 하다.
안녕하세요 파파이썬입니다. 저도 이번주제 문제는 다른 주제 문제 보다는 조금 코드가 조금은 간결하더라구요:). 글 잘 보고 갑니다!
내일도 파이팅!