[C++] 백준(BOJ) - 2293 : 동전 1

12 Apr 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 2293 : 동전 1(링크)

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 $2^{31}$보다 작다.

알고리즘

1. DP
2. 경우의 수

풀이

• 모든 경우의 수 누적
• 0개를 뽑는 경우의 수는 1개이다

코드

// BOJ - 2293 : 동전 1
#include <bits/stdc++.h>
using namespace std;

int n, k, dp[10004], tmp;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;

	dp[0] = 1; // 아무것도 넣지않는 경우의 수 1
	for (int i = 0; i < n; i++)
	{
		cin >> tmp;
		for (int j = tmp; j <= k; j++)
		{
			dp[j] += dp[j - tmp];
		}

		/*for (int l = 0; l <= k; l++)
		{
			cout << dp[l] << " ";
		}
		cout << '\n';*/
		///
		/// dp  0 1 2 3 4 5 6 7 8 9 10
		///  1  1 1 1 1 1 1 1 1 1 1 1
		///  2  1 1 2 2 3 3 4 4 5 5 6
		///  5  1 1 2 2 3 4 5 6 7 8 10 
		///
	}

	cout << dp[k];
	return 0;
}

평가

• 0개를 뽑는 경우의 수는 1가지