2294번 : 동전2

문제를 보면 숨이 막힙니다. 어떻게 풀지 감도 안오는 경우가 많죠.

생각을 조금 다르게 하면 오히려 쉬운 문제가 될 수 있습니다.

동전의 가치에 초점을 두지 않고, 동전의 개수와 가치의 합에 초점을 두는 것이죠.

우선 변수들의 범위부터 파악을 해봅시다.

동전의 가치는 총 100개까지 입력받을 수 있습니다.

동전의 가치는 100000보다 작거나 같은 수 입니다.

가치의 합은 최대 1부터 10000까지입니다.

그러면 이제 dp테이블을 설계해봅시다.

dp[i]가 무엇을 뜻해야 값이 쌓일 수 있을까요? 굳이 dp[i-1]과 dp[i]가 관련될 필요는 없습니다.

네. 많은 풀이가 있겠지만 저는 dp[i]=가치의 합이 i원이 될 때의 최소 동전 개수 로 정의하였습니다.

이때 가치의 합은 최대 100000이 될 수 있으니 dp[100001] 이렇게 선언해두어야겠죠

그럼 값을 어떻게 쌓아야할까요?

만약 arr 배열에 동전의 가치가 오름차순으로 나열되어 있을 때, dp[i]는 i보다 작은 dp값에 arr에 있는 동전 1개를 더한 값일 겁니다.

예를 들면, 동전은 1, 2, 3, 7이 있다고 가정합시다.

이때 dp[13]은...

1) dp[12]에 1을 더한 값 (1은 동전 한개를 의미함)

2) dp[11]에 1을 더한 값

3) dp[10]에 1을 더한 값

4) dp[6]에 1을 더한 값

5) 1)~4)의 dp값이 모두 존재하지 않으면 dp[13]은 -1. (주어진 동전으로 만들 수 없는 가치의 합)

이 5개 중 하나가 될것입니다.

이를 코드 옮겨봅시다. 

우선 초기화는 arr에 들어온 값들은 dp에서 무조건 1의 값을 갖습니다. 즉 동전 한개만 써서 만들 수 있는 가치의 합을 미리 설정해 두는 겁니다.

그리고 나머지 dp값들은 -1로 초기화 해둡니다.

본격적으로 반복문을 돌려봅시다. 가장 큰 반복문(i)(은 1부터 문제에서 주어진 가치의 합까지 총 k번 반복합니다.

이때 dp[i]==1 이면 해당 가치의 합은 이미 최솟값인 1로 정해져 있으므로(앞서 초기화 한 값들) continue 로 넘어갑니다.

안쪽 반복문(j)는 arr을 탐색해야 하니 1부터 n까지 반복해야 합니다. 지금부턴 주석으로 설명하겠습니다.

if (arr[j] >= i) break;

//탐색하려는 arr[j]의 값이 현재의 가치의 합인 i보다 커지면 더이상 돌필요가 없으므로 탈출.

if (dp[i - arr[j]] == -1) continue;

//dp[i]가 그 어떤 동전으로도 가치의 합을 구할 수 없을 때에 해당하므로 넘어갑니다.

else {

//else 안에 들어온다 == 가치의 합을 구할 수 있다.

if (dp[i] == -1) dp[i] = dp[i - arr[j]] + 1;

//dp[i]의 값을 처음 바꿀 때는 별다른 조건 없이 값을 변경해줍니다.

else if (dp[i - arr[j]] + 1 < dp[i]) dp[i] = dp[i - arr[j]] + 1;

//dp[i]의 값을 이미 바꾼 적이 있다면 둘 중 더 작은 값으로 변경해줍니다.

}

이렇게 하고 마지막 출력은 dp[k]를 출력해주면 됩니다.

#include <stdio.h>

#include <algorithm>

using namespace std;

int dp[100001], n, k;

int arr[101]; // 동전의 가치가 순서대로 들어감.

int main() {

scanf("%d %d", &n, &k);

arr[0] = 0;

for (int i = 1; i <= n; ++i) {

scanf("%d", &arr[i]);

}

for (int i = 0; i <= 10000; ++i) {

dp[i] = -1;

}

sort(arr, arr + n+1);

for (int i = 1; i <= n; ++i) {

dp[arr[i]] = 1;

}

for (int i = 1; i <= k; ++i) {

if (dp[i] == 1) continue;

for (int j = 1;j<=n; ++j) {

if (arr[j] >= i) break;

if (dp[i - arr[j]] == -1) continue;

else {

if (dp[i] == -1) dp[i] = dp[i - arr[j]] + 1;

else if (dp[i - arr[j]] + 1 < dp[i]) dp[i] = dp[i - arr[j]] + 1;

}

}

}

printf("%d", dp[k]);

}

*여담으로 이 문제의 정답률이 낮은 이유는 dp를 설계할 때 범위를 잘못 줘서일꺼라고 예상합니다.(예를 들어 dp[10001]이라던지..)