[ALGORITHM] 8. 다이나믹 프로그래밍

이것이 취업을 위한 코딩테스트다 with python 문제 풀이

8-5. 실전문제 '1로 만들기'

# C8. 다이나믹 프로그래밍 - 실전문제 '1로 만들기'

import sys
put = sys.stdin.readline

# 그리디로 elif문 써서 큰 수 순서대로 하면 안 되는 이유
# 맨 처음에 5로 나누는 것보다 1 빼고 시작하는 게 더 작은 케이스가 있을 수 있다!
# 그래서 부분문제로 나누고, 기존 연산값 재활용하는 dp로 해야 함

x = int(put())
d = [0]*30001 # DP 테이블 초기화

# x = 1일 때는 이미 1로 만들어졌으니까 연산 필요 없음 -> 2부터 시작
for i in range(2, x+1):
    # 뒤에 붙은 +1은 계산한 횟수 더하는 것!
    # -1, /2, /3, /5한 케이스 '모두' 계산한 후 그 중 최솟값을 고르고 +1 하면 됨

    # n이 7일 때 n에서 1을 빼는 연산 횟수 1번과, 6을 1로 만드는 d[6] 값을 더하면 d[7] 값 나옴. d[7] = d[6] + 1

    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i-1] + 1

    # min(d[i] + 1, d[i // 5] + 1)가 아닌 이유는 
    # 1 빼는 케이스 하면서 d[i]에 +1 이미 해줘서.
    # min(d[i], d[i // 5] + 1)는
    # min(d[i-1] + 1, d[i // 5] + 1)와 동일. 
    # -1하는 케이스, 나누는 케이스 '모두' 한 후 그 중 최솟값 고르기! 
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1) 
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)    
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)

print(d[x])

 

8-6. 실전문제 '개미 전사'

# C8. 다이나믹 프로그래밍 - 실전문제 '개미 전사'

import sys
put = sys.stdin.readline

# i-1번째를 털면 현재(i번째)의 식량 창고는 못 함(연속돼서)
# i-2번째를 털면 현재(i번째)와 함께 털 수 있음
# a(i) = max(a(i-1), a(i-2) + k)

n = int(put())
foods = list(map(int, put().split()))

d = [0]*101 # dp 테이블 초기화

d[0] = foods[0] # 원소가 하나면 최대값은 자기 자신
d[1] = max(foods[0], foods[1]) # 두 개면 최대값은 둘 중 최대

for i in range(2, n):
    d[i] = max(d[i-1], d[i-2] + foods[i])

print(d[n-1]) # 리스트가 0부터 시작해서

 

8-7. 실전문제 '바닥 공사'

# C8. 다이나믹 프로그래밍 - 실전문제 '바닥 공사'

import sys
put = sys.stdin.readline

# 2×n 크기의 직사각형을 1×2, 2×1, 2x2 덮개로 채우는 방법의 수를 구하기 

n = int(put())
d = [0]*1001 # dp 테이블 초기화

# n = 1 -> 세로의 1개
# n = 2 -> 세로 / 가로1 + 2*2짜리 하나의 3개
# n = 3 -> 세로 / 가로2 + 2*2 2개의 5개

# i-1은 2*1의 하나
# i-2는 1*2 타일 2개나 2*2타일 하나로 하는 2가지 경우 (2*1로 하는 경우는 i-1에서 커버됨)

d[1] = 1
d[2] = 3
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]*2

print(d[n] % 796796)

 

8-8. 실전문제 '효율적인 화폐 구성'

# C8. 다이나믹 프로그래밍 - 실전문제 '효율적인 화폐 구성'

import sys
put = sys.stdin.readline

# 화폐 종류 최소한으로 이용해 가치 합이 m원이 되도록
# 큰 단위 화폐가 작은 단위의 배수가 아니라 그리디 말고 dp로 풀어야

n, m = map(int, put().split())
worth = [int(put()) for _ in range(n)]

# 2, 3원으로 7원 만들기
# d[금액] = 화폐 개수
# d[5]는 d[3] + 1(2원)으로 만들 수 있음
# d[7]는 d[5] + 1(2원)으로 만들 수 있음
# d[7]는 d[7]이랑 d[i-k] + 1 중 최솟값

d = [10001]*(m+1) # dp 테이블 초기화

d[0] = 0 # 0원은 화폐 하나도 안 썼을 때 만들 수 있음
for money in worth:
    for i in range(money, m+1): # 화폐 단위보다 작은 값은 어차피 갱신될 필요도 없음
        # 이전(현재금액 - 화폐단위) 인덱스에 값이 존재하면 현재금액 해당 값 갱신 가능
        if d[i - money] != 10001:
            # 기존 d[i]랑 새로 갱신된 d[i - money] + 1 중 최솟값
            d[i] = min(d[i], d[i - money] + 1)

if d[m] == 10001: print(-1) # M원을 만드는 방법이 존재하지 않으면
else: print(d[m])