[Algorithm] BOJ 동전 1 - 2293번

 

 

 

1. 문제 풀이

n 가지 종류의 동전으로 그 가치의 합이 k원이 될 수 있는 경우의 수를 구하는 문제이다. 각각의 동전은 몇개라도 사용할 수 있다.

(1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 으로 주어진다.

우선 해당 값을 만들 수 있는 경우의 수는 값의 배수 일때 1번.

순열으로 만들었을때 두가지 동전으로 만들 수 있는 경우의 수 = 이전 동전으로 만들 수 있는 경우의 수 + 현재 동전으로 만들 수 있는 경우의 수 가 되는것이다.

이것을 점화식으로 인덱스에 기록해가며 더해가면 해당 동전들로 가능한 경우의 수를 구할 수 있다.

처음 첫 인덱스에 값을 1로 설정하고 그 뒤를 0으로 초기화해 처음 coin의 값이 들어갈 때 1이 더해지도록 했다.

 

 

2. 코드

#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
	int n,k;
	//동전 종류 수
	cin >> n;
	//가치
	cin >> k;
	int coin;
	//가치크기 배열 1, 0 ... 초기화
	int	val[k + 1] = ;
	for (int j = 0; j < n; j++)
	{
		cin >> coin;
	//코인의 값을 받아 i에 설정, 코인의 값만큼 이전 인덱스 값을 더해가며 저장
		for (int i = coin; i < k + 1; i++)
			val[i] += val[i - coin];
	}
	cout << val[k] << endl;
	return 0;
}

3. 채점 기록

메모리 : 2016KM / 0ms