공부 : 동빈나 유튜브 < (이코테 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))
'study > 알고리즘' 카테고리의 다른 글
[알고리즘/백준] 2644번 촌수계산 (0) | 2021.12.09 |
---|---|
[알고리즘] 다이나믹 프로그래밍(LIS) - 병사 배치하기 (0) | 2021.12.08 |
[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 1 (0) | 2021.12.03 |
[알고리즘/프로그래머스] 그리디 - 조이스틱 (0) | 2021.12.02 |
[알고리즘/프로그래머스] 2019 KAKAO BLIND RECRUITMENT - 실패율 (0) | 2021.11.26 |