백준 2293번: 동전 1

[문제 링크]

2293번: 동전 1

---

top-down 방식으로 풀어보려다 너무 많은 시간을 허비한 문제였다.

동전의 순서만 다른 경우를 가려내기 위해선 2차원 dp 배열을 선언해야 하는데 dp[101][10001] 으로 선언하게 되면 메모리가 4mb를 넘게되어 메모리 초과가 발생하게 된다.

 

bottom-up 방식으로 풀었더니 코드도 훨씬 간결하고 쉽게 풀렸다. 

 

틀에 박힌 사고를 개선해야 한다는 것을 다시한번 느끼게 된 문제였다.

---

#include <iostream>
using namespace std;

int n, k, pay[101], memo[10001];

int Bottomup(int k)
{
	memo[0] = 1;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++)
			if(j - pay[i] >= 0)
				memo[j] += memo[j - pay[i]];

	return memo[k];
}

int main(void)
{
	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		cin >> pay[i];

	cout << Bottomup(k) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 77 day