[BOJ2293 C++] 동전 1

골드 5 문제 ..

근데 진짜 알듯말듯하면서 안되니까 진짜 짜증..

뭔가 패턴이 있는게 분명한데 생각보다 쉽게 안보인다.

처음부터 막 생각해서 하면 좋겠지만, 지금은 생각을 좀 해보다가 안풀리면

풀이를 보고 기술을 익혀서 다음에 비슷한 문제가 나오면 풀 수 있게 하려고 함

이번 문제에서는 모든 경우를 한번에 생각하지 않고,

점화식을 DP[n] = DP[n] + @ 이런 식으로 쓰면서,

하나 하나씩 하면서 완성해가는 기술이 있더라.

문제는 다음과 같다.

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

구성이 같은데 순서가 다른 것은 같은 경우이다 -> 여기서 바로 계단을 못쓴다.

뭐 어떻게 억지로 생각하면 할 수 있겠지만 그건 진짜 무식한거지

잘 풀더라고 .. . 다들 ..

coins	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
1, 2	1	2	2	3	3	4	4	5	5	6
1, 2, 5	1	2	2	3	4	5	6	7	8	10

위 표를 보면 ..

우선 Arr를 k만큼 선언 후, 0으로 초기화 한다.

그리고 DP[0] = 1 로 놓고,

동전을 하나하나씩 추가된다고 생각하면서 표를 업데이트 한다.

위 표처럼 2차원을 만들고 업데이트 하는게 아니라,

하나의 행만 두고 동전을 추가하면서 업데이트 하는 식으로!

동전이 1만 있는 1행의 경우 먼저 해보면

DP[N] = DP[N] + DP[N-1]
-> DP[N]은 모두 0으로 되어 있었고,
DP[0]은 1이므로, DP[1] = DP[1] + DP[0] = 0 + 1 = 1
DP[2] = DP[2] + DP[1] = 0 + 1 ] = 1
...
해서 표처럼 coins 1인 경우 한 행이 완성된다.

다음 동전이 1과 2가 있는 경우.

1에 대한 경우의 수는 이미 DP안에 녹아 있다고 생각.

그래서 새로 추가된 동전 2 만 신경 쓰면서 업데이트 한다.

DP[N] = DP[N] + DP[N-2]
DP[1]은 N-2가 안되니까 패스
DP[2] = DP[2] + DP[0] = 1 + 1 = 2
...
DP[4] = DP[4] + DP[2] = 1 + 2 = 3

이런식으로 DP를 다시 업데이트 시킨다.

똑같이 1, 2로 만들 수 있는 경우의 수를 모두 체크 했으면,

동전 5를 추가해서 다시 DP를 업데이트 한다.

DP[0~4] 는 동전 가 추가되도 업데이트가 안되므로 패스

DP[5] = DP[5] + DP[0] = 3 + 1 = 4
DP[6] = DP[6] + DP[1] = 4 + 1 = 5
...
DP[10] = DP[10] + DP[5] = 10

해서 최종적으로 동전 1, 2, 5 를 써서 10이라는 값을 만드는 방법은 이렇게 10가지다..

뭔가 직접 해보기도 했는데 패턴찾기가 생각보다 쉽지가 않다..

이번에 그래도 익혔으니까. 잘 기억해뒀다가 써먹도록 하자.

//
// Created by 신성준 on 2023/03/05.

//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, k;
    cin >> N >> k;
    int dp[10001] = {0,};
    int coins[101];
    for(int i = 1; i <= N; i++){
        cin >> coins[i];
    }

    dp[0] = 1;
    for(int i = 1; i <= N; i++){ //코인 갯수만큼 DP 업데이트
        for(int j = coins[i]; j <= k; j++){ //N원 이상인 것부터 업데이트가 되니까
            dp[j] = dp[j] + dp[j - coins[i]];
        }
    }
    cout << dp[k];
}