[백준 9084번 C/C++] 동전

 

[백준 9084번 C/C++] 동전

 

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

 

9084번: 동전

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는

www.acmicpc.net

---

 

해결전략

 

Dynamic Programming 다이나믹 프로그래밍, 동적계획법

배낭 문제

 

---

 

해설

 

dp[ i ][ j ] 

---

 

 

코드

 

#include <iostream>
#include <vector>
using namespace std;
 
int t, n, m; //t 테스트 케이스 수, n 동전의 가지 수, m 목표 금액
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
	cin >> t;//t 테스트 케이스 수 입력
	
	while (t--)
	{
		cin >> n; //n 동전의 가지 수 입력
		vector<int> coins(n+1);
		for (int i = 1; i <= n; i++)
		{
			cin >> coins[i];
		}
 
		cin >> m; //m 목표 금액 입력
 
		//dp[][]는 i개의 동전 종류를 사용했을때 j원(금액)을 만들 수 있는 경우의 수 //i의 동전 종류는 동전 종류 입력순
		vector<vector<int>> dp(n+1, vector<int>(m+1));
		dp[0][0] = 1; //0원을 만드는 방법은 아무 동전도 사용하지 않는 경우 1가지 방법이 있다.
 
		for (int i = 1; i <= n; i++) 
		{
			for (int j = 0; j <= m; j++) //주의! j는 0부터 시작!
			{
				dp[i][j] = dp[i - 1][j]; //이전 동전까지 사용한 경우의 수 복사
 
				if (j >= coins[i])
					dp[i][j] += dp[i][j - coins[i]]; //i번째 동전을 사용하여 j원을 만들 수 있는 경우의 수를 더한다.
			}
		}
 
		//
		cout << "\n";
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++)
			{
				cout << dp[i][j] << " ";
			}
			cout <<"\n";
		}
		//
 
		cout << dp[n][m] << "\n"; 
	}
 
 
	return 0;
}

 

 

---

 

다른 풀이

 

#include <iostream>
#include <vector>
using namespace std;
 
int t, n, m; //t 테스트 케이스 수, n 동전의 가지 수
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
	cin >> t;
	
	while (t--)
	{
		cin >> n;
		vector<int> coins(n+1);
		for (int i = 1; i <= n; i++)
		{
			cin >> coins[i];
		}
 
		cin >> m;
 
		/* 방법 1: 이중배열 dp
		//dp[][]는 i개의 동전 종류를 사용했을때 j원(금액)을 만들 수 있는 경우의 수 //i의 동전 종류는 동전 종류 입력순
		vector<vector<int>> dp(n+1, vector<int>(m+1));
		dp[0][0] = 1; //0원을 만드는 방법은 아무 동전도 사용하지 않는 경우 1가지 방법이 있다.
 
		for (int i = 1; i <= n; i++) 
		{
			for (int j = 0; j <= m; j++) //주의! j는 0부터 시작!
			{
				dp[i][j] = dp[i - 1][j]; //이전 동전까지 사용한 경우의 수 복사
 
				if (j >= coins[i])
					dp[i][j] += dp[i][j - coins[i]]; //i번째 동전을 사용하여 j원을 만들 수 있는 경우의 수를 더한다.
			}
		}
 
		cout << dp[n][m] << "\n";
		*/
 
		//방법 2: 단일배열을 사용하여 더 빠른 방법
		vector<int> dp(m + 1, 0);
		dp[0] = 1; //0원을 만드는 방법은 아무 동전도 사용하지 않는 경우 1가지 방법이 있다.
 
		for (int i = 1; i <= n; i++) {
			for (int j = coins[i]; j <= m; j++) 
			{
				dp[j] += dp[j - coins[i]];
			}
		}
 
		cout << dp[m] << "\n";
 
	}
 
	return 0;
}

 

 

 

---

 

유사문제

 

2023.07.24 - [코딩테스트/백준] - [백준 2293번 C/C++] 동전 1

 

[백준 2293번 C/C++] 동전 1

[백준 2293번 C/C++] 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,00

designerd.tistory.com

 

---