반응형
동전 1
-
BOJ) 동전 1알고리즘/백준 2020. 7. 18. 21:56
동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 n 가지 종류의 동전을 각각 여러개 이용해서 k원이 되게 하는 수를 구하는 문제다. 처음에는 dfs로 접근했다가, 동전은 몇개라도 사용할 수 있다는 조건을 보고 DP로 선회했다. 각각 동전에 대해서 K원 이하일 때, 쓰일 수 있는 모든 돈에 경우의 수를 추가시켜주었다. for문을 돌면서 각 동전 coin에 대해coin의 가치부터 K원 까지 들어갈 수 있는 경우만 추가시켜주면 해결되는 문제였다. 코드 import java.io.BufferedReade..