[정올] 여객선 (Cruise)

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=2720&sca=99 

JUNGOL

문제부터 요약해보면, 

 

용량이 정해진 배들에 무게를 가진 사람들을 태웁니다. 이 때, 사람들을 모두 태우고 출항하지 않고 남은 배들의 무게의 총합이 최대가 되도록 만드는 것이 목표입니다. 출력은 남은 배들의 무게 총합을 출력해야 합니다.

 

<Solution>

아이디어는 총 3가지 정도로 구성됩니다.

1. 배를 순열로 배치해서 태울수 있는 사람들을 모두 태워봅니다. (DFS) (순열로 생각해야 하는 이유는 1, 2를 타는것과 2, 1을 타는게 다를 수 있기 때문) 2. 이 때 사람을 태우는 과정은 prefix sum과 binary upper bound 찾기를 사용합니다. 3. 가지치기 합니다.

 

일단 1번과 2번만 사용하게 되면, 아래와 같은 코드가 구성됩니다. 

 

[prefix sum과 binary search 이용]

#include <iostream>
using namespace std;
#define MAXB (16)
#define MAXN ((int)1e5)
int B, N;
int S[MAXB+10];
int usedS[MAXB+10];

int P[MAXN+10];
int prefix_P[MAXN+10];

int ans;

void InputData(){
    cin >> B >> N;
    for (int i=0; i<B; i++){
        cin >> S[i]; // 0번 index부터
    }
    for (int i=1; i<=N; i++){
        cin >> P[i]; // 1번 index부터
    }
}

int s, e; // start index는 계속 써야하므로

void dfs(int how_many_picked){ // 배 몇개 골랐는지 현재까지

    // 사람을 모두 사용했고, 배도 B개 이하로 골랐으면 성공
    if(s > N && how_many_picked <=B){
        int tmp = 0;
        for(int i = 0; i<B; i++){
            if(!usedS[i]) tmp+= S[i];
        }
        ans = max(ans, tmp);
        return;
    }
    // 배는 다썼는데 사람이 다 못탔음 실패
    if(how_many_picked >=B && s<=N){
        return;
    }

    for(int i = 0; i<B; i++){
        if(usedS[i]) continue;

        usedS[i] = 1;
        // 배에 승객 최대한 태움
        // prefix sum array이용
        // 배의 용량을 넘지않는 최대 값 (binary search)
        int e = N;
        int sol = -1;
        int s_before = s; // 복구를 위해
        while(e>=s){
            int mid = (s+e)/2;
            if(prefix_P[mid] - prefix_P[s_before-1]<= S[i]){
                s = mid+1;
                sol = mid;
            }
            else{
                e = mid-1;
            }
        }
        s = sol+1; // 시람 여기까지 썼으니까

        dfs(how_many_picked+1);
        // 원상복구

        usedS[i] = 0;
        s = s_before;

    }
}

void solution(){
    //build prefixsum
    for(int i = 1; i<=N; i++){
        prefix_P[i] = prefix_P[i-1] + P[i];
    }

    s = 1;
    ans = -1;
    // 9! 순열 (36만정도)
    dfs(0);

}

int main(void){

    InputData();//입력받는 부분

    //여기서부터 작성
    solution();

    cout << ans << endl;//출력하는 부분
    return 0;
}

하지만 이 경우 TLE가 나는 것을 알 수 있습니다. 

 

여기서 가지치기를 생각해 보아야하는데,

총 두가지 가지치기를 생각할 수 있습니다.

1. 남은 배들이 모두 남아도 이미 구한 답보다 작거나 같은경우 더이상 진행하지 않아도 된다. 2. 사용한 배가 동일할 때, 사람을 더 많이 태운 경우만 진행해도 된다.

이렇게 두가지 경우를 위해 

void dfs(int how_many_picked, int left_cost, int used)

dfs 함수에 left_cost와 used를 추가해줍니다. 

그리고 left_cost의 경우 초기에 전체를 더해주고 빼는 형태로 하면 쉽게 구현이 가능합니다.

 

다음으로 used의 경우 bit연산으로 checking을 할 수 있게 해주었습니다. 

 

만약 index 0, 1, 2번 배를 사용했다면, 순서가 0 -> 1 -> 2 이든 2 -> 0 -> 1 이든 무관하게 used 의 값은 2진법 2b111 즉 10진법 7의 값을 가질 것입니다. 따라서 매번 어디까지 사람들이 사용되었는가를 used에 맞게 기록할 수 있는 array를 하나 두고, 만약 이전에 기록된 사람 수 보다 덜 사용되는 경우 가지치기를 해서 더이상 진행하지 않게 하여도 됩니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
using namespace std;
#define MAXB (16)
#define MAXN ((int)1e5)
int B, N;
int S[MAXB+10];

int P[MAXN+10];
int prefix_P[MAXN+10];

int memorize_s[1<<16];

int ans;

void InputData(){
    cin >> B >> N;
    for (int i=0; i<B; i++){
        cin >> S[i]; // 0번 index부터
    }
    for (int i=1; i<=N; i++){
        cin >> P[i]; // 1번 index부터
    }
}

int s, e; // start index는 계속 써야하므로

void dfs(int how_many_picked, int left_cost, int used){ // 배 몇개 골랐는지 현재까지

    // 사람을 모두 사용했고, 배도 B개 이하로 골랐으면 성공
    if(s > N && how_many_picked <=B){
        ans = max(ans, left_cost);
        return;
    }
    // 배는 다썼는데 사람이 다 못탔음 실패
    if(how_many_picked >=B && s<=N){
        return;
    }

    // 가지치기 
    // 남은 배들이 모두 남아도 ans보다 안좋은경우
    if(left_cost <= ans) return;


    for(int i = 0; i<B; i++){
        if(used & 1<<i) continue;

        used |= 1<<i;
        // 배에 승객 최대한 태움
        // prefix sum array이용
        // 배의 용량을 넘지않는 최대 값 (binary search)
        int e = N;
        int sol = -1;
        int s_before = s; // 복구를 위해
        while(e>=s){
            int mid = (s+e)/2;
            if(prefix_P[mid] - prefix_P[s_before-1]<= S[i]){
                s = mid+1;
                sol = mid;
            }
            else{
                e = mid-1;
            }
        }
        s = sol+1; // 시람 여기까지 썼으니까
		
        // 가지치기
        if(memorize_s[used] <s){
            dfs(how_many_picked+1, left_cost - S[i], used);
            memorize_s[used] = s;
        }

        
        // 원상복구
        used &= ~(1<<i);
        s =s_before;
    }
}

void solution(){
    //build prefixsum
    for(int i = 1; i<=N; i++){
        prefix_P[i] = prefix_P[i-1] + P[i];
    }

    s = 1;
    ans = -1;
    // calculate total sum 
    int total_cost = 0;
    for(int i = 0;i<B; i++){
        total_cost+= S[i];
    }
    // 9! 순열 (36만정도)
    dfs(0, total_cost, 0);

}

int main(void){

    InputData();//입력받는 부분

    //여기서부터 작성
    solution();

    cout << ans << endl;//출력하는 부분
    return 0;
}