백준 2293 c++ "동전 1" -PlusUltraCode-

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

 

[필자 사고]

LIS 문제를 이용한 dp문제이다.

다만 다른점은 경우의 수를 구해야 되는 것이다.

LIS문제는 +1형태로 계속 누적하는 거지만 경우의 수는

이전 수를 += 형태로 더해나가야 된다.

 

필자는 +=이 부분을 생각을 하지 못하여 풀지 못했다.

경우의 수는 누적 더하기라는 교훈을 알게 되었다.

[코드 해설]

2. 입력 처리 (Input 함수)

Input() 함수는 먼저 표준 입력을 통해 동전의 개수(N)와 목표 금액(K)을 입력받는다. 이후, 동전 정보를 저장할 coin 벡터를 크기 N+1로 할당하고, 결과를 저장할 dp 벡터를 크기 K+1로 초기화한다.
그 후, 사용자가 입력한 동전의 가치를 coin 벡터에 저장한다.

3. DP를 이용한 해결 (Game_Start 함수)

이 함수에서는 다이나믹 프로그래밍을 활용하여 특정 금액(K)을 만들 수 있는 경우의 수를 계산한다.
먼저 dp[0]을 1로 설정하여, 아무 동전도 사용하지 않고 0원을 만드는 경우를 하나로 인정한다.
그 후, 동전들을 오름차순으로 정렬한 뒤, 작은 단위의 동전부터 차례대로 처리한다.

각 동전에 대해, 해당 동전을 사용하여 만들 수 있는 모든 금액을 순회하며 경우의 수를 누적한다.
이 과정에서 dp[j]는 coin[i]를 포함하여 j원을 만들 수 있는 경우의 수를 의미하며, dp[j - coin[i]] 값을 더해 기존 경우의 수를 확장한다.

4. 프로그램 실행 (main 함수)

프로그램은 다음과 같은 흐름으로 실행된다.

1. Input() 함수를 호출하여 사용자 입력을 받는다.
2. Game_Start() 함수를 호출하여 다이나믹 프로그래밍 배열을 채운다.
3. 최종적으로 dp[K] 값을 출력하여, 목표 금액(K)을 만들 수 있는 모든 경우의 수를 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

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);
	for (int i = 1; i <= N; i++) {
		cin >> coin[i];
	}
}

void Game_Start() {
	dp[0] = 1;
	sort(coin.begin() + 1, coin.end());

	for (int i = 1; i <= N; i++) {
		for (int j = coin[i]; j<=K; j++) {
			dp[j] += dp[j - coin[i]];
		}
	}
}

int main(void) {
	Input();
	Game_Start();
	cout << dp[K];
}