[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 2

공부 : 동빈나 유튜브 < (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 >
         + 책 < 이것이 취업을 위한 코딩테스트다 >

 

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

 

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 만들기

이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분

 

첫째줄에 N, M ( 1<=N<=100, 1<=M<= 10000)

이후에 N개의 줄에 각 화폐의 가치가 주어짐, 화폐의 가치는 10000보다 작거나 같은 자연수

불가능할 때는 -1 출력

 

입력 예시	출력 예시
2 15 2 3	5
3 4 3 5 7	-1
2 5 2 3	2

 

직접 작성한 코드 - 1

 

처음에 입력 예시 1, 2만 보고 짰다가 같은 수끼리의 곱셈으로 만들어지는 수일때만 

답이 출력되도록 코드를 짰다.

 

N, M = map(int, input().split())
coin_list = []

coin_num = [0] * (M + 1)

for i in range(N):
    coin_list.append(int(input()))

for i in range(1, M+1):
    for coin in sorted(coin_list):
        if i % coin == 0:
            coin_num[i] = coin_num[i-coin]+1

answer = coin_num[M] if coin_num[M] != 0 else -1
print(answer)

 

(최종) 직접 작성한 코드 - 2

 

min 함수를 이용하려면 0으로 초기화할 수 없다.

따라서 조건보다 더 큰 값인 10001으로 초기화를 시켜준다.

그리고 coin_num[0]을 0으로 초기화시켜준다.

 

min 함수를 사용하여 그 값의 효율적인 화폐 구성을 저장해준다.

 

N, M = map(int, input().split())
coin_list = []

coin_num = [10001] * (M + 1)
coin_num[0] = 0

for i in range(N):
    coin_list.append(int(input()))

for i in range(1, M+1):
    for coin in sorted(coin_list):
        coin_num[i] = min(coin_num[i-coin]+1, coin_num[i])

answer = coin_num[M] if coin_num[M] != 10001 else -1
print(answer)

 

 

실전문제 - 금광

 

n * m 크기의 금광이 있다. 금광은 1*1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 

채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 

맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다.

이후 m-1번에 걸쳐 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다.

결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램 작성

 

첫째 줄에 테스트 케이스 T가 입력 (1<=T<=1000)

매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력 (1<=n, m<=20)

둘째 줄에 n*m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력 (1 <= 각 위치에 매장된 금의 개수 <= 100)

 

직접 작성한 코드

 

오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 하는 것을

if else문으로 쓰기 싫어서 리스트 슬라이싱을 사용하였다.

범위를 벗어나지 않게 하기 위해서 0으로 각 테두리를 추가해주었다.

그리고 np.array의 transpose 함수를 사용하였다.

 

--> 답안 예시에는 if else문으로 짜여있다. 내가 푼 풀이대로 짜기 위해서 시간이 많이 걸렸다.

실제 코테에서는 시간 싸움이라 코드를 간결하게 짜는것도 중요하지만 빨리 푸는 것도 중요할 듯..

 

import numpy as np

def max_gold(gold_list, n, m):
    miner = [[0]*(n+2) for _ in range(m+2)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            miner[i][j] = max(max(miner[i-1][j-1:j+2])+gold_list[i-1][j-1], miner[i][j-1])
    return max(miner[m])


T = int(input())

for i in range(T):
    n, m = map(int, input().split())
    gold_list = []
    test_case = list(map(int, input().split()))
    for j in range(n):
        gold_list.append(test_case[j*m:j*m+m])
    print(max_gold(list(np.array(gold_list).T), n, m))