[틀림] 백준 1480 보석모으기 // 가방여러개 dp

https://www.acmicpc.net/problem/1480

* 시도1

N이작다? -> 조합이 여러번?(이 보석은 저가방에 넣고 ... 저 보석은 저가방에...) -> 비트마스크?

무게작은순으로 정렬하면 되나?(그리디?) 

 

* 풀이

그리디보다는 무식하게 완탐으로 시작할것.

보석의 idx가 아닌, 가방의 상태들로 dfs 실행.

상태를 생각해보자.

[가방idx][남은용량][현재까지담은 보석의 집합]

포인트는 가방기준 dfs, 현재까지담은 보석의 집합을 상태로 두는 것이다.

현재가방에 보석을 담는다 or 안담는다로 완탐. & 메모

보석은 for문으로 dfs내에서 완탐 필요.

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

ll n,m,c;
ll a[24];
ll dp[14][24][1<<14];

//(가방인덱스, 남은용량, 현재까지담은보석집합)
ll dfs(ll idx, int cap , int yam) {
    if(idx==m) {
        return 0;
    }

    ll & ret = dp[idx][cap][yam];
    if(ret!=-1) return ret;

    //현재가방에 보석을 안담는 경우
    ret = max(ret,dfs(idx+1,c,yam));  //다음가방의 capacity 초기화

    //담는경우
    for(int i=0;i<n;++i) { //보석하나씩 탐색
        int isBeforeYam = (1<<i) & yam; //이전에 넣었던 보석인가
        int isYam = (cap - a[i]) >=0 ; //넣을수있는 보석인가(용량내)
        if(!isBeforeYam && isYam) {
            ret = max(ret, dfs(idx,cap-a[i],yam | (1<<i))+1); //보석갯수 +1
            //주의 : idx+1하면안됨
            //현재 가방에서 더 담을수 있음.
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    memset(dp,-1,sizeof(dp));
    cin>>n>>m>>c;
    for(int i=0;i<n;++i) {
        cin>>a[i];
    }

    cout<<dfs(0,c,0);
    
    return 0;
}

 

* dp없이 안되나요?

dp 없이 이 문제를 풀면 시간복잡도를 분석해보겠습니다.

문제를 이해해보면:

• n개의 보석
• m개의 가방
• 각 가방의 용량은 c
• 각 보석의 크기는 a[i]
• 보석은 서로 다른 가방에 담아야 함
• 최대한 많은 보석을 담아야 함

dp를 사용하지 않는 경우, 모든 가능한 경우를 탐색하는 완전 탐색(브루트 포스) 방식으로 풀어야 합니다.

시간복잡도 분석:

• 각 보석에 대해 담거나 담지 않는 선택 -> 2^n 가지 경우
• 담는 경우 어떤 가방에 담을지 선택 -> m 가지 경우
• 담을 수 있는 보석인지 확인 -> O(1)

따라서 기본적인 완전 탐색의 시간복잡도는 O(m * 2^n)입니다.

하지만 실제로는 조금 더 복잡합니다. 보석을 담을 때 각 가방의 남은 용량을 고려해야 합니다. 최악의 경우, 가방 각각에 대한 상태를 모두 고려해야 하므로 O(m * 2^n * c^m)와 같은 복잡도가 될 수 있습니다.

하지만 문제의 특성상 보석을 담는 순서를 고려하고 용량 제약을 처리하면 시간복잡도는 O(n! * m)에 가까워집니다. 왜냐하면:

• n개의 보석을 어떤 순서로 담을지 결정하는 경우의 수: n!
• 각 보석을 m개의 가방 중 어디에 담을지 결정: m

결론적으로, DP 없이 이 문제를 해결하면 시간복잡도는 O(n! * m)으로, 지수 시간이 소요됩니다. 이는 n이 작더라도 계산이 매우 오래 걸릴 수 있습니다.