알고리즘

[백준] 2293 동전1 : C++ 풀이

https://boj.kr/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 배낭문제를 활용하는 알고리즘이라는데, 전 다이나믹 프로그래밍이 더 자연스러운 것 같았습니다. 중간에 메모리 초과가 나와서 더 당황했네요. 해당 문제는 자연수의 분할 문제로 생각해서 볼 수 있습니다. 다만 분할될 수 있는 자연수의 종류가 제한된 경우이죠. 동전이라서 처음엔 아무 생각 없이 그리디라고 생각하고 보았으나, 제일 큰 동전의 개수를 기준으로 메모이제이션 하면 되니 DP 문제에 가까웠습니다. 문제의 예시를 기준으로 생각해보..