[BOJ] 2293번 동전1(C++)

BOJ 2293번 <동전 1>
난이도 : 골드 5
알고리즘 분류 : DP

DP 유형의 문제를 많이 풀어보지 않아서 접근방식에 애를 먹었다.

N개 유형의 동전이 주어지고 이를 이용해 K원을 만드는 총 경우의 수를 구하는 문제다.
다만 같은 동전을 같은 갯수를 쓰되 순서만 다른 케이스는 모두 같은 케이스로 취급한다.

케이스 별로 분류를 해야하는데, 마지막에 사용한 동전의 타입 을 기준으로 삼았다.

ex)
동전의 종류 : 1 2 5
목표 금액 : 10

dp[0] = 1 // 0원을 만드는 방식은 아무런 동전도 사용 안하는 방법 1가지
dp[1] = 1
dp[2] = dp[1](마지막에 1원사용) + dp[0](마지막에 2원사용) : 2
dp[3] = dp[2](마지막에 1원사용) + dp[1](마지막에 2원 사용) : 3 (X)

하지만 dp[i-1] 최종값을 완성시키고 dp[i] 를 계산할 경우 문제가 생긴다.

void solve() {
	dp[0] = 1;
	for (int i = 1; i <= N; i++) { // 각 동전
		for (int j = coin[i]; j <= K; j++) { 
			dp[j] += dp[j - coin[i]];
		}
	}
	cout << dp[K];
}


void input() {
	for (int i = 1; i <= N; i++) {
		cin >> coin[i];
	}
}

int main() {
	cin >> N >> K;
	input();
	solve();
}

위의 코드가 성공적인 접근이였다.

핵심코드 solve()

void solve() {
	dp[0] = 1;
	for (int i = 1; i <= N; i++) { // 각 동전
		for (int j = coin[i]; j <= K; j++) { 
			dp[j] += dp[j - coin[i]];
		}
	}
	cout << dp[K];
}

1. 각 동전별로 dp 값을 쌓아나간다 -> 바깥 for문
2. j - coin[i] >= 0 을 만족해야한다. -> 안쪽 for문

2번의 의미는 N 코인을 사용하기 위해서는 K 값이 N보다는 크거나 같아야한다는 뜻이다.
따라서 그 이상 값부터 dp 값을 쌓아나간다.