[C++] BOJ_2293 동전 1

문제: 백준 2667 (c++)

풀이과정

---

문제를 보면 조건에서 사용한 동전의 구성이 같은데, 순서만 다르다면 같은 경우로 본다는 내용이 있다.

이 조건을 생각하며 풀이를 해봤을 때

동전이 1, 2, 5가 있을 경우 우선 dp[0]에 1을 넣음으로써 아무것도 선택하지 않을 경우를 보장해 주고

---

동전 1로 10을 만드는 경우를 본다면

1로 1을 만들 경우 = 1
1로 2를 만들 경우 = 1 + 1
1로 3을 만들 경우 = 1 + 1 + 1

dp[i] = dp[i] + dp[i-1] 이라는 것을 알 수 있다.

---

동전 2로 10을 만드는 경우를 본다면
2로 0, 1을 만들 수 없기에

2로 2를 만들 경우 = (1+1), 2
2로 3을 만들 경우 = (1+1+1), 1+2
2로 4를 만들 경우 = (1+1+1+1), 1+1+2, 2+2

dp[i] = dp[i] + dp[i-2] 라는 것을 알 수 있다.

( 괄호 안의 방법 ex) ‘1+1’ )-> 이미 전 단계에서 1로 2를 만드는 경우이다.
dp는 누적이기에 이전 동전으로 만든 방법의 수도 포함시켜야 한다는 것을 잊으면 안 된다.

---

dp[j] = dp[j] + dp[j - a[i]] ;

위의 설명에 대한 코드이다.

---

전체 코드이다.

#include <iostream>
using namespace std ;

int main(){

    int n ;
    int k ;

    cin >> n >> k ;

    int dp[10001] = {0} ;
    int a[101] ;

    dp[0] = 1 ;

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

    for(int i = 0; i < n; i++){
        for(int j = a[i]; j <= k ; j++){
            dp[j] = dp[j] + dp[j - a[i]] ;
        }
    }
    
    cout << dp[k] ;
}