[C++] BOJ(백준) 2294 동전 2

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

2294번: 동전 2

 

DP 문제다.

 

이전 값들의 접근으로 배열을 이용했다.

입력 받은 가치들을 배열에 저장하고 그 값들을 탐색했다.

동전의 가치를 더해서 원하는 수를 만들 수 있기 때문에

dp[원하는 값 - 가치] + 1을 하면 그 값을 만들기 위한 동전의 수를 알 수 있다.

모든 가치의 값들을 탐색하면서 그 중 최솟값을 찾는다.

 

주의할 점은

1. 배열의 범위를 벗어나선 안된다.

즉, 원하는 값 - 가치가 음수나 0이 되어선 안된다.

 

2. dp[원하는 값 - 가치]의 값이 0이어서는 안된다.

0인 경우, 해당 값까지 도달할 방법이 없다는 뜻이므로 여기에 1을 더해주는 경우는 제외해야 한다.

 

3. 최솟값을 찾아야 하므로 dp의 초기값은 계산될 수 있는 값보다 큰 값으로 지정해야 한다.

기본인 0으로 두면 무조건 최솟값은 0이 된다.

 

#include <iostream>
using namespace std;

int arr[100];
int dp[100001];

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k;	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		// 입력 받는 값들은 항상 결과가 1
		dp[arr[i]] = 1;
	}

	for (int i = 1; i <= k; i++) {
		// 입력 받은 값들만 dp 값이 1이고 그 값들은 계산해 줄 필요 없음
		if (dp[i] == 1) continue;

		// 초기 값을 0으로 설정, 0으로 두면 아래 min에서 무조건 0으로 계산됨
		dp[i] = 1000000;

		// 입력 받은 값은 규칙이 없기 때문에 입력 받은 값의 배열을 탐색하기 위함
		for (int j = 0; j < n; j++) {
			// 범위를 벗어나면 continue
			if (i - arr[j] < 1) continue;

			// 값이 0이면 해당 숫자에 도달하는 방법이 없으므로 continue
			if (!dp[i - arr[j]]) continue;

			// 현재 값과 이전 값에 + 1더한 값 중 최솟값을 저장
			dp[i] = min(dp[i], dp[i - arr[j]] + 1);
		}

		// 위의 반복문에서 모두 continue로 dp값을 변경하지 못했다면 초기값 0으로 되돌림
		if (dp[i] == 1000000) dp[i] = 0;
	}

	// 값이 있으면 출력, 아니면 -1 출력
	if (dp[k]) cout << dp[k];
	else cout << -1;
}

말로 풀어쓰는 건 여전히 어렵다.

포항항ꉂꉂ(ᵔᗜᵔ*)