반응형
기타줄
-
BOJ) 기타줄알고리즘/백준 2020. 7. 22. 15:16
기타줄 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 첫째 줄에 갈아야하는 기타 줄의 수 n과 기타줄 브랜드 수 m이 공백을 두고 주어진다. 다음 m줄에 대해서 각 브랜드의 기타줄 패키지 가격과 1개의 가격이 차례대로 주어진다. 이 때, 기타줄을 갈 수 있는 최소 가격을 구하는 문제다. dfs로 dp로 할까 생각하다가 dfs로 먼저 짜봤다. 하지만, n이 최대 100이어서 빠르게 손절했다. (가지치기를 한다해도 비효율적) 다음은 dp를 생각했다. 줄 하나를 갈 때, 2개를 갈 때, ... n개를 갈..