백준 9084 c++ "동전" -PlusUltraCode-

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

 

 

[필자 사고]

배낭문제를 응용한 문제이다.

이 문제를 풀면서 새로운 사고를 얻었다. 바깥 반복문은 동전 종류 수만큼 반복문을 돌리고

안쪽 반복문은 동전을 시작점으로 받아서 하나하나 갯수를 갱신해주는 방식이다.

 

여기서 실수한 부분은 매번 갱신한다는 의미는 값을 덮어쓰는게 아닌 이전 값과 더해주는 연산을 해줘야 된다.

 

새로운 사고를 얻을 수 있는 문제라서 좋았다.

아래는 자세한 코드 해설이다.

[코드 해설]

1. 입력 처리 (Input 함수)

Input() 함수는 테스트 케이스마다 필요한 데이터를 입력받고 초기화하는 역할을 합니다.

• N (사용 가능한 동전의 개수)을 입력받습니다.
• 동전의 금액을 입력받아 coin 벡터에 저장합니다.
• totalMoney (만들어야 할 금액)를 입력받습니다.
• 동적 계획법을 수행하기 위해 dp 벡터를 totalMoney + 1 크기로 초기화합니다.

2. 동적 계획법을 이용한 방법 수 계산 (Game_Start 함수)

이 함수는 배낭 문제 (DP, Knapsack 방식) 를 활용하여 각 동전을 사용하여 특정 금액을 만드는 방법의 수를 계산합니다.

• dp[0] = 1로 설정하여, 아무 동전도 사용하지 않고 0원을 만드는 경우의 수는 1 이라는 초기값을 설정합니다.
• 각 동전 coin[i]에 대해 dp[k] 값을 갱신합니다.
  • k가 coin[i] 이상일 때, dp[k] += dp[k - coin[i]]를 수행하여 해당 동전을 추가하는 경우의 수를 누적합니다.
• 최종적으로 dp[totalMoney] 값을 출력하면, totalMoney를 만드는 모든 방법의 수를 얻을 수 있습니다.

3. 테스트 케이스 실행 (main 함수)

• T (테스트 케이스의 개수)를 입력받습니다.
• T번의 반복문을 수행하며, Input()과 Game_Start()를 실행합니다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<long> dp;
vector<int> coin;
int T;
int N;
int totalMoney;
void Input() {
	cin >> N;
	coin.clear();
	dp.clear();
	coin.resize(N + 1);
	
	for (int i = 1; i <= N; i++) {
		cin >> coin[i];
	}

	cin >> totalMoney;
	dp.resize(totalMoney + 1);
}

void Game_Start() {
	dp[0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int k = coin[i]; k <= totalMoney; k++) {
			dp[k] += dp[k - coin[i]];
		}
	}

	cout << dp[totalMoney] << '\n';
}

int main(void) {
	cin >> T;
	while (T--) {
		Input();
		Game_Start();
	}
}