백준 2293번: 제출
[ 문제 설명 ]N가지 종류의 동전을 사용하여 가치의 합이 K원이 되도록 만들 때, 가능한 경우의 수를 구하는 문제입니다.동전의 구성은 같지만 순서가 다른 경우는 같은 경우로 간주합니다.동전은 여러 개 사용할 수 있습니다.[ 문제 해결 방법 ]✅ 기본적인 DP 접근법이 문제는 **동전의 조합 문제이므로 동적 계획법(DP)**을 활용해야 합니다.dp[i]: i원을 만드는 경우의 수점화식:dp[j] += dp[j - coin]초기값: dp[0] = 1 (0원을 만드는 방법은 아무 동전도 사용하지 않는 1가지 경우)3. 메모리 초과 문제 분석기본적인 DP 접근법으로 구현할 경우, 다음과 같은 실수가 발생할 수 있습니다.❌ 메모리 초과 원인불필요한 2차원 배열 사용dp[N][K] 형태로 2차원 배열을 사용하면 ..
Algorithm
2025. 4. 1. 10:50