BOJ 2293 (동전 1)

• 문제
  n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
  
  사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
  
  
• 입력
  첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
  
  
• 출력
  첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

#include<iostream>
using namespace std;
int n, k, answer;
int coinValue[101];
int DP[10001];
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void input()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> coinValue[i];
	}
}
void checkAnswer()
{
	DP[0] = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = coinValue[i]; j <= k; j++)
		{
			DP[j] += DP[j - coinValue[i]];
		}
	}
}

int main()
{
	fast_io();
	input();
	checkAnswer();
	cout << DP[k];
	return 0;
}

   처음에 문제를 보고 완전 탐색 방식이 떠올랐으나 시간 제한이 0.5초라 시간 초과가 100퍼 나올 것이라 다른 알고리즘 적용을 해야했다. 해결 방안이 바로 떠오르지 않아 알고리즘 분류를 봤더니 DP를 활용해야 하는 문제였다.

출력 조건에서 경우의 수는 2^31보다 작다고 했으므로 int 자료형을 써도 될 것 같다고 판단

예를 들어 5원짜리를 활용하여 1원부터 10원까지 만드려고 할 때 1~4원까지는 절대 만들 수 없고 5원은 0원에서 5원을 더하면 가능하다 -> DP[5]=DP[0]+DP[5]
6원은 1원에 5원을 더하면 가능하여 DP[6]=DP[6]+DP[1] 이런 방식으로

DP[찾고자 하는 금액-현재 동전의가치]를 입력받은 동전의 가치마다 계산하여 누적시킨다면 원하는 결과를 얻을 수 있다.

처음에 0원 -> 아무것도 안고르는 1가지 경우의 수로 설정해주는 것이 중요한 포인트 같다.

시간 복잡도 : O(N^2)

숏코딩

풀이 방법이 하나밖에 없는 것 같다