(BOJ 2293 동전1) 중복 거르기; 조합의 수 구하기 DP

문제 자체는 평범함.

n개의 서로 다른 종류의 동전 조합해서 (사용 개수 제한 X) k원을 만드는 경우의 수 구하기.

 

내가 헤멘 부분은,

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

---

Sol 1) (WA) 생각없이 짠 DP

만약 1, 2, 3원짜리 동전이 있다고 하자.

k원을 만들려면, k-1 / k-2 / k-3 원에 각각 1 / 2 / 3원을 더하면 되잖아?

DP[i] : i원을 만들 수 있는 경우의 수

DP[k] = sum(DP[k-coin[i]]) (where k-coin[i] >= 0) 인가?

 

=> 반례 존재. k = 5라고 하자.

DP[5] = DP[4] + DP[3] + DP[2] 일텐데,

DP[3]의 경우의 수에 2원짜리 추가해서 5를 만드는 것; 3 + 2 = 5

DP[2]의 경우의 수에 3원짜리 추가해서 5를 만드는 것엔 겹치는 경우의 수가 존재; 2 + 3 = 5

하나 빼줘야 하는데, general한 케이스로 올라가면 몇 개가 겹칠지 모름 (아마 엄청 겹칠 것)

---

Sol 2) (구현 불가) '이전에 선택한 동전의 수 정보'를 넘겨주기

동전을 어떤 순서로 고르는 건 의미가 없다;

몇 개 골랐는지 정보가 중요하고, 그게 서로 겹치지 않아야 서로 다른 경우의 수로 인정받을 수 있다

ex) 5를 만들기 위해... (1 : 2개 / 2 : 0개 / 3 : 1개), (1 : 1개 / 2 : 2개 / 3 : 0개), ...

 

(예를 들어)

5-2원의 정보들에 2원짜리 1개를 더해서 정보를 수정하여 5원 정보로 넣자.

만약 같은 정보가 이미 있으면 (5-3원에서 얻은), 걸러낼 수 있도록

(set 같은데에 insert하는걸 이용해서 자동으로 걸러지게 하면 되겠다고 생각)

최종적으로 k원을 만들 수 있는 정보의 개수를 구하면, 그게 k원을 만들 수 있는 경우의 수가 되겠지.

 

처음엔 각 가치 (0~K원) 마다 set<string>을 가질 수 있도록 vector<set<string>>을 선언하고,

지금까지 어떤 동전을 몇 개 골랐는지 string 정보로 넘겨주려고 함 (bit-masking 처럼).

그래서, 동일한 정보 string이 있으면 알아서 중복이 걸러지도록!

 

근데, 생각해보니까, 9개 초과해서 고르면 자릿수가 다음 자리로 넘어가서 string의 각 character만 이용해서 정보를 담기엔 부족함.

그렇다고, set<string> 대신 vector<int> 써서 각 셀에 동전 사용 개수를 저장하기엔, 벡터는 서로 비교하기 오래걸려서 중복 검사가 어렵겠구나 함.

'이전에 골랐던 동전 개수의 정보'를 넘겨주는 방법은 아쉽지만 망한 듯

---

Sol 3) DP

아래 블로그에 소개된 영상 보고 DP 풀이 이해함.

velog.io/@ready2start/Python-%EB%B0%B1%EC%A4%80-2293-%EB%8F%99%EC%A0%84-1

[Python] 백준 - 2293 동전 1

www.youtube.com/watch?v=2IkdAk1Loek&t=551s

DP[i][k] : i번째까지의 동전만 사용 (단, i번째는 반드시 한 번 이상 사용) 해서 k원을 만드는 경우의 수

특이한 점은, i번째를 반드시 한 번 이상 사용 & i번째 동전까지만 사용한다는 점

ex) 1, 2, 3로 5를 만들 때, DP[2][3]은 1 2만 사용하되 2를 반드시 1번 이상 사용해서 3을 만들어야 함. 

 

점화식은 DP[i][k] = sum(DP[j][k-coin[i]) (j = 0~i, where k-coin[i] >= 0)

ex) DP[2][3] = DP[2][1] + DP[1][1]

 

점화식이 너무 뜬금 없을 수도 있는데, 테이블을 직접 채워보면 '아!' 느낄 수 있다.

k-coin[i]를 통해 '반드시 i번째 동전을 1번 쓰는 조건'을 만족하고,

j를 i이하로 잡아서 'i번째까지의 동전만 사용하는 조건'을 만족시킨다.

 

이러면, 각 DP[i][k]는 unique한 경우의 수만 가지게 됨 (i번째는 반드시 한 번 이상 사용하고, i번째 이하의 동전만 사용)

답은, DP[i][K]의 값을 모두 더한 것 (i : 0~N)

 

int N, K;
vi coins;
int dp[100][10001];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N >> K;
    coins = vi(N, 0);
    FOR(i, 0, N) cin >> coins[i];
    sort(all(coins)); // just in case

    // init dp; others at 0
    FOReq(k, coins[0], K) {
        if(k % coins[0] == 0) dp[0][k] = 1;
    }

    FOR(i, 1, N) FOReq(k, coins[i], K) {
        int& cur = dp[i][k];
        if (k - coins[i] > 0) {
            for (int j = i; j >= 0; j--)
                cur += dp[j][k - coins[i]];
        }
        else if (k - coins[i] == 0)
            cur++;
    }

    int ans = 0;
    FOR(i, 0, N) ans += dp[i][K];
    cout << ans;
}

 

---

그러나, 백준 문제에선 4MB의 메모리 제한이 있었음.

즉, 2차원 DP 테이블을 쓰지 말라는 소리.

 

다행히 계산 순서만 조작해서, 같은 로직을 유지한 채로 DP 테이블만 1차원으로 줄일 수 있다.

코인 i = 0 to N-1까지 순회하며, 각 코인마다 0~K 까지의 DP를 채운다.

즉, FOR(i, 0, N) FOReq(k, coins[i], K) 

 

이러면, 첫번째 코인을 계산하고 두번째 코인을 계산할 땐

자동으로 첫~두번째 코인의 결과값만 가지고 DP를 계산하므로 위의 조건들을 만족한다.

 

DP[k] : k원을 만들 수 있는 경우의 수 (중복 제외)

DP[k] = sum(DP[k-coins[i]])

 

int N, K;
vi coins;
int dp[10001];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N >> K;
    coins = vi(N, 0);
    FOR(i, 0, N) cin >> coins[i];
    sort(all(coins)); // just in case

    dp[0] = 1;
    FOR(i, 0, N) FOReq(k, coins[i], K) {
        int& cur = dp[k];
        if (k - coins[i] >= 0) {
            cur += dp[k - coins[i]];
        }
    }

    cout << dp[K];
}

---

배운점) 중복되는 경우를 거르는 로직 공부 + DP테이블 불필요한 차원 줄이기

(분명히 익혀두면 어딘가에선 쓸 듯)