백준 2293 동전1

재귀로 호출했고 int[10001][101]을 메모이제이션으로 이용.

풀이방식은 

DP(won,k) = DP(won - C[k] * 1) + DP(won - C[k] * 2) + ... + DP(won - C[k] * (won/C[k]) )

라고 생각해서 고대로 나타냈다.

won은 돈, C[k]는 k번째 코인의 가격이다.

 

근데 이대로 풀어서 맞으려면 coinWorth배열, 즉 동전의 가격을 정렬해야 하는데, 왠지 입력을 오름차순으로 친절하게 줄것 같아서 그냥 제출했다.

오답뜨면 그때 오름차순 해보지 머~ 하고 대충 생각함 ㅎ

메모이제이션으로 활용한 배열인 memo[i][j] 는 'j개의 코인으로 i돈을 만들기 위한 가짓 수'이다

처음 시도한 코드.

#include <iostream>
using namespace std;
int memo[10001][101];

int solve(int won, int n) {
	if (memo[won][n] > 0) {
		return memo[won][n];
	}
	if (n < 0) {
		return 0;
	}
	if (won < 0) {
		return 0;
	}
	if (n == 0) {
		if (won % coinWorth[n] == 0) return memo[won][n] = 1;
	}

	int result = 0;
	int limit = (int)(won / coinWorth[n]);
	for (int i = 0; i <= limit; i++) {
		result += solve(won - coinWorth[n] * i, n - 1);
	}

	return memo[won][n] = result;
}

int main() {
	int coinN, resultWon;

	cin >> coinN >> resultWon;

	for (int i = 0; i < coinN; i++) {
		cin >> coinWorth[i];
	}

	int result = solve(resultWon, coinN - 1);

	cout << result << endl;
}

근데 오답이 아니라 메모리초과가 뜨더라

멍청한 나는 재귀때문인줄 알고 반복문으로 고쳤다

근데 멍청해서 반복문으로 고치는 것도 넘넘 오래 걸려따

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int coinWorth[101];
int memo[10001][101];


int main() {
	int coinN, resultWon;

	cin >> coinN >> resultWon;

	for (int i = 0; i < coinN; i++) {
		cin >> coinWorth[i];
	}

	int i = 0;
	while (true) {
		if ((coinWorth[0] * i > resultWon)) break;
		memo[(coinWorth[0] * i)][0] = 1;
		i++;
	}

	for (int j = 1; j < coinN; j++) {
		for (int i = 0; i <= resultWon; i++) {
			for (int k = 0; k <= i / coinWorth[j]; k++) {
				memo[i][j] += memo[i - (int)(coinWorth[j] * k)][j - 1];
			}
		}
	}
	
	int result_final = memo[resultWon][coinN - 1];

	cout << result_final << endl;
}

코드 길이가 줄긴 했는데

당연히 메모리 초과 ㅎ

메모리 제한이 4MB인걸 그제서야 찾았다

아 백만짜리 int를 써서 그런건가.. 싶어서 곰곰히 생각해봤다.. 이걸 줄일수 있나

멍청해서 곰곰히가 아니라 고되게 생각한 끝에 

'아! memo[i][j]를 구할때는 memo[i][j-1]만 있으면 돼는구나!'

싶어서 

아래와 같이 구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int coinWorth[101];
int memo[10001];
int prevMemo[10001];

int main() {
	int coinN, resultWon;

	cin >> coinN >> resultWon;

	for (int i = 0; i < coinN; i++) {
		cin >> coinWorth[i];
	}

	int i = 0;
	while (true) {
		if ((coinWorth[0] * i > resultWon)) break;
		memo[(coinWorth[0] * i)] = 1;
		i++;
	}

	for (int j = 1; j < coinN; j++) {
		for (int x = 0; x <= resultWon; x++) {
			prevMemo[x] = memo[x];
			memo[x] = 0;
		}
		for (int i = 0; i <= resultWon; i++) {
			for (int k = 0; k <= i / coinWorth[j]; k++) {
				memo[i] += prevMemo[i - (int)(coinWorth[j] * k)];
			}
		}
	}
	
	int result_final = memo[resultWon];

	cout << result_final << endl;
}

맞췄다!

근데 맞추고 나서 안건데

http://hsp1116.tistory.com/23

이걸 보니까....

허참.... 내가 더 멍청해보인다

힝...