코딩/백준 (Python)
백준 2294: 동전2 (Python)
접근 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 전형적인 DP 문제여서 점화식을 파악하는 과정이 중요했다. 이전 단계인 2293번 '동전 1' 문제를 풀고오면 조금 수월하게 접근할 수 있는것 같다. 합이 K 일 때, 사용한 동전의 최소 개수를 구하기 위하여, 합이 i 일 때 사용한 최소 동전의 개수를 구하는 작은 문제로 쪼개었다. DP 배열을 K + 1 의 길이로 생성하고, DP[i]의 의미를 합이 i 일 때..
2023. 4. 14. 23:41
최근댓글