[성실코딩 10일차] 백준 #2293 동전1 / DP

아악 오늘 풀고 자고 싶었는데 졸작 하루종일 하다가 시간 다 썼다

전역변수 int형 2차원 배열로 선언하면 메모리초과 ! int 범위 숫자, 최대 배열 선언 크기 이런 것들 찾아서 알아두고 있어야지~

일단 동적할당하면 메모리 초과 해결할 수 있습니당

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//int DP[101][10001];
vector<vector<int>> DP;
int coin[101]; // 코인 종류
int n, res;

int main() {

	// 입력
	int n;
	cin >> n >> res;
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}

	DP.assign(n,vector<int>(res+1,0));

	// 정렬
	sort(coin,coin+n);

	
	//DP채우기
	for (int i = 0; i < n; i++) { // 코인 종류 수
		DP[i][0] = 1;  // 초기화 -> 본인으로 나눴을 경우를 위해
		for (int j = 1; j <= res; j++) { // 만들고 싶은 금액 결과 값
			// 현재 값을 더하지 않았을 때, 그 금액의 경우의 수 
			if (i==0 && j>=coin[i]) {
				DP[i][j] = DP[i][j-coin[i]];
			}
			else if (i > 0) {
				if ( j>=coin[i]) {
					DP[i][j] = DP[i][j - coin[i]] + DP[i - 1][j];
				}
				else if ( j<coin[i]) {  
					DP[i][j] = DP[i - 1][j];
				}
			}
		}
	}


	//출력
	cout << DP[n-1][res] << endl;

	return 0;
}