백준 2294 c++ "동전 2" -PlusUltraCode-

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

 

[필자 사고]

필자는 처음에 이 문제를 접근할 때 2차원 DP를 생각했었다.

dp[i][n] 이라고 할 때 값어치 n은 동전의 값을 정했었다.

 

문제를 해결하지 못하였고 다른 분들의 코드를 참고할 결과 1차원 DP를 이용하여 풀 수 있었다.

coin을 이용하여 현재 idx - coin 의 dp값이 0이 아니면 min으로 최소값비교한느 형식으로 문제를 풀 수있었다.

이 문제를 풀면서 느낀점은 DP문제는 직접 처은 경우의 수를 직접 세어서 점화식을 찾아야 될거 같다.

[코드 해설]

1. 입력 처리 (Input 함수)

Input() 함수는 사용자로부터 동전의 개수 NNN과 목표 금액 KKK를 입력받고, 이를 바탕으로 필요한 벡터를 초기화하는 역할을 한다.

• coin 벡터는 동전의 가치를 저장하며, 입력값에 따라 크기를 조정한다.
• dp 벡터는 동전 조합을 이용해 목표 금액을 만들기 위한 최소 동전 개수를 저장하며, 처음에는 INT_MAX로 초기화된다.
• 이후, N개의 동전 가치를 입력받아 coin 벡터를 채운다.

---

2. 동전 조합을 이용한 최소 개수 계산 (Game_Start 함수)

Game_Start() 함수는 동적 계획법(DP)을 사용하여 목표 금액 KKK를 만들기 위한 최소 동전 개수를 구하는 역할을 한다.

• dp[0] = 0으로 설정하여, 0원을 만드는 데 필요한 동전 개수는 0임을 명시한다.
• 각 동전에 대해 coin[i] 이상의 금액을 만들 수 있도록 dp 배열을 갱신한다.
• dp[k] = min(dp[k], dp[k - coin[i]] + 1)을 통해 현재 동전을 사용했을 때 최소 동전 개수를 업데이트한다.
• 만약 목표 금액 KKK를 만들 수 없다면 dp[K]는 여전히 INT_MAX 상태이므로 -1을 출력한다. 그렇지 않다면 dp[K] 값을 출력한다.

---

3. 메인 함수 (main 함수)

main() 함수는 Input() 함수를 호출하여 입력을 처리한 후, Game_Start() 함수를 실행하여 결과를 도출하는 역할을 한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int N, K;
vector<int> coin;
vector<int> dp;

void Input() {
	cin >> N >> K;
	coin.resize(N + 1);
	dp.resize(K + 1,INT_MAX);

	for (int i = 1; i <= N; i++) {
		cin >> coin[i];
	}
}

void Game_Start() {
	dp[0] = 0;
	for (int i = 1; i <= N; i++) {
		for (int k = coin[i]; k <= K; k++) {
			if (dp[k - coin[i]] != INT_MAX) {
				dp[k] = min(dp[k], dp[k - coin[i]]+1);
			}
		}
	}
	if (dp[K] == INT_MAX) cout << -1;
	else cout << dp[K];
}

int main(void) {
	Input();
	Game_Start();
}