1. 문제

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

2. 아이디어

▷ 이 문제는 DP를 사용하여 해결할 수 있다.

▷ 배열 coins에는 동전의 가치를,
    배열 dp에는 동전을 이용하여 k원이 되도록 할 때 사용하는 동전의 최소 개수를 저장한다.

▷ 우선 dp[0] = 0로 설정한다.
    0원을 만들기 위해서 어떤 동전도 사용하지 않으면 되기 때문이다.

▷ 로직: dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
    처음에는 dp[j] = dp[j - coins[i]] + 1가 적절하다고 생각했다. 그러나 예제를 살펴보니 이상한 점이 보였다. 첫번째 for문에서 i가 1일 때(1원과 5원을 이용하여 15원을 만들 때) 필요한 최소 동전개수는 3개이다. 그리고 i가 2일 때(1원, 5원, 12원을 이용하여 15원을 만들때) 필요한 최소 동전개수는 4개이다. dp[j] = dp[j - coins[i]] + 1 이 경우 dp[15]가 4로 갱신되는 문제점이 발생하게 된다.

▷ k원을 만들 수 없는 경우는 상수 unable로 처리한다.
    로직에서 min을 이용하므로 초기값으로는 이보다 더 큰 값이 들어가 있고 for문을 돌며 이 값이 갱신되어야 한다. 따라서 unable을 10001로 정의해 두었다. n = 1, k = 10000인 경우 동전을 가장 많이 사용하게 되고 이때 사용하는 동전의 개수는 10000개이다. 이보다 동전을 더 많이 사용할 수는 없으므로 unable을 10001로 하는 것이 적절하다 판단하였다.

3. 해결 코드

#include <iostream>
#include <cstring>
using namespace std;

int n, k;
int coins[101] = { 0 };
int dp[10001] = { 0 };
#define unable 10001

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// 입력
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> coins[i];
	
	for (int i = 0; i <= k; i++) dp[i] = unable;

	// 로직
	dp[0] = 0; // 0원을 만드는 방법: 어떤 동전도 선택하지 않는다.
	for (int i = 0; i < n; i++) {
		for (int j = coins[i]; j <= k; j++) {
			dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
		}
	}

	// 출력 및 종료
	if (dp[k] == 10001) cout << -1 << '\n';
	else cout << dp[k] << '\n';

	return 0;
}

4. 틀린 코드

#include <iostream>
#include <cstring>
using namespace std;

int n, k;
int coins[101] = { 0 };
int dp[10001] = { 0 };
#define unable 10001

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// 입력
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> coins[i];
	memset(dp, unable, sizeof(dp));

	// 로직
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = coins[i]; j <= k; j++) {
			dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
		}
	}

	// 출력 및 종료
	if (dp[k] == unable) cout << -1 << '\n';
	else cout << dp[k] << '\n';

	return 0;
}

1) 문제점

해결코드는 for문을 돌며 배열을 초기화하였고 틀린 코드의 경우 memset이라는 함수를 이용하여 배열을 초기화하고자 하였다.

memset(dp, unable, sizeof(dp));

92%에서 계속 오류가 떴고 찾아보니 예외처리가 되지 않았을 때 발생하는 상황이라고 한다. 디버깅을 해보았는데 memset함수를 수행한 뒤 dp의 값이 unable(10001)이 아니라 다른 숫자로 세팅되어 있었다.

2) 배운점

https://cplusplus.com/reference/cstring/memset/을 살펴보면
memset은 메모리 블록을 채운다고 한다. 메모리 블록은 1byte(8bit)단위로 채워지기 때문에 4byte로 표현하는 int타입의 숫자를 우리가 의도한 대로 표현할 수 없다.


예제

int arr[4];
memset(arr, 1, sizeof(arr));

위 상황에서 arr 배열의 각 값에

따라서 memset은 0 또는 NULL로 초기화하거나, char타입 변수를 초기화할 때 사용하는 것이 적절하다!!