[C] 백준 2294번 : 동전 2

 

오늘도 새로운 문제를 풀어보았습니다 ! (ʃƪ ˘ ³˘) 

문제를 얼마나 더 풀어야,,, 한 번에 맞히는 날이 올까요 ?_?

 

백준 2294번

https://www.acmicpc.net/problem/2294

2294번: 동전 2

 

이 문제를 처음 읽고는 약간의 고민?에 빠지게 되었습니다.

dp 배열을 사용해서 값을 계속 최적화해나가면 될 것 같긴 한데,

dp 배열의 index를 동전으로 잡을지 아님 가치로 잡을지가 조금 헷갈렸습니다.

.

저는 처음에 for문의 반복 횟수를 줄이려고 ①index를 동전 개수로 잡았습니다.

즉, 'dp[동전개수] = 최대 가치'라고 사용한 것입니다.

이렇게 하면 for문의 반복 횟수 자체는 줄어들지만, 답을 구하는 데 문제가 발생합니다.

주어진 동전을 사용하여 가치 k를 맞출 수 있더라도, 최적화된 값이 아니라면 탈락될 수 있기 때문입니다.

.

따라서 저는 ②dp의 index를 가치로 잡았습니다. (dp[가치] = 최소 동전 개수)

여기서 또 고민이 된 점은,

'만약 dp[j]라는 값을 구하는데 주어진 동전의 조합으로 j를 만들 수 없으면 어떻게 할까?' 였습니다.

저는 이러한 경우는 dp의 value를 0으로 처리하였습니다.

.

다음은 제가 구현한 코드입니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int input[101];
int dp[10001];

int MIN(int x, int y)
{
	if (x == 0)
		return y;
	else if (y == 0)
		return x;
	return x < y ? x : y;
}

int main() {

	int n, k;
	
    	// 입력
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &input[i]);

	// dp 배열 구하기
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			for (int u = 1; u <= k; u++) {
				if (j < u*input[i])
					break;
				if (dp[j - u * input[i]] == 0)
					if (j - u * input[i] != 0)
						break;
				dp[j] = MIN(dp[j], dp[j - u * input[i]] + u);
			}
		}
	}

	// 출력
	if (dp[k]==0)
		printf("%d", -1);
	else
		printf("%d", dp[k]);

	return 0;
}

 

다시 보니깐 코드가 좀 조잡한 것 같네요..^^

우선 저는 주어진 동전을 여러 번 사용할 수 있다고 했기 때문에 for문을 한번 더 사용하였습니다. (곱셈용)

그리고 제일 안쪽 for문의 반복 횟수를 줄여주기 위해 break 문을 더해주었습니다.

또한 저는 MIN 함수를 통해 최솟값을 구하려고 했는데 이미 dp 배열을 0으로 초기화한 상태였기 때문에,

(최솟값이 계속 0으로 나옴...)

dp의 value가 0인 경우는 예외 처리를 따로 해주었습니다.

.

이렇게 코드를 짜서 제출을 하고 보니 정답이긴 한데,,

시간도 오래 걸리는 것 같고, 무엇보다도 코드가 조잡한 것 같아서 다른 분들의 코드를 참고해보았습니다.

다음은 새로 구현해본 코드입니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int input[101];
int dp[10001];

int MIN(int x, int y)
{
	return x < y ? x : y;
}

int main() {

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

	for (int i = 1; i <= n; i++)
		scanf("%d", &input[i]);

	for (int i = 1; i <= k; i++)
		dp[i] = 100001;

	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = input[i]; j <= k; j++) {
			dp[j] = MIN(dp[j], dp[j - input[i]] + 1);
		}
	}

	if (dp[k]==100001)
		printf("%d", -1);
	else
		printf("%d", dp[k]);

	return 0;
}

 

3중 for문을 쓰는 것이 마음에 걸렸는데, 이를 2중 for문으로 줄였습니다.

굳이 for문을 하나 더 사용하여 곱셈을 처리해주지 않더라도,

최적화를 반복하다 보면 곱셈의 효과(?)를 낼 수 있다는 것을 알게 되었습니다.

.

또한 저는 dp 배열을 0으로 초기화하고, 최솟값을 구하는 것이 큰 고민이었습니다. (조건을 덕지덕지 덧붙였음..ㅠ)

이것은 dp를 index 1부터 k까지는 최댓값 +1로, index 0은 0으로 초기화하면 해결할 수 있습니다.

나 바보인가?..

.

아무래도 dp 문제는 좀 더 풀어봐야 할 것 같습니다..^^ㅠ