[Jungol] 정올 2270 여객선(Cruise)

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1983&sca=9040

 

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

최대 수용무게가 10인 배를 이용해서 1, 2번째 승객을 태운 다음, 

최대 수용무게가 15인 배를 이용해서 3, 4, 5, 6번째 승객을 태우면

최대 수용무게가 12인 배를 출항하지 않으므로 최적이 된다.

 

① 배들을 배치하는 경우의 수 = B! = B × (B-1) × (B-2) × ... × 1

ex) 1, 2, 3 → [1 2 3], [1 3 2], [2 1 3], [2 3 1], [3 1 2], [3 2 1] ▶ DFS 탐색

 

배들이 배치되었을 때, 마지막에 출항하지 않은 배들의 수용무게 합을 최대화하는 방법은

앞쪽에 배치된 배의 최대 수용인원 만큼 태우고 출항시키는 것입니다.

ex) 10 15 12 순서로 배를 배치했을 때,

    [6 + 3 = 9] → [3 + 2 + 3 + 7 = 15] → [ ]로 해서

    출항하지 않은 배들의 최대 수용무게 = 12가 될 수 있습니다.

 

② 부분합(psum[]) 이용

배들이 배치된대로 for문을 이용해서 탑승 가능 여부를 확인할 수 있지만

psum을 이용해서 정해진 배(pivot)에 최대 탑승인원을 구할 수 있습니다.  ▶ 이분탐색, Upper Bound

 

ex) 배 배치 순서 = [10 15 12], 탑승 대기 인원 = [6 3 3 2 3 6 3 3]이며

     첫 번째 배에 [6 + 3]인원 탑승 완료한 상태일 때, 두번째 배에 탑승시킬 수 있는 인원은?

     즉, 최대 수용무게 15인 배에 남은 인원 [6 3 3 2 3 6 3 3]이 최대 몇명 탑승할 수 있는가?

[이분 탐색 없이 단순 for문으로 이용하는 경우]

마지막 탑승인원 위치 = 2 → s

① 3 ~ 8번째까지 탑승하는 경우

    탑승 인원 무게 psum[8] - psum[2] = 29 - 9 = 20 ← 3 + 2 + 3 + 6 + 3 + 3

    탑승 하고자 하는 배의 최대 수용 무게 15 < 20(= 탑승하고자 하는 인원의 총 무게)이므로 8번째까지 탑승 불가

② 3 ~ 7번째까지 탑승하는 경우

    탑승 인원 무게 psum[7] - psum[2] = 26 - 9 = 17 ← 3 + 2 + 3 + 6 + 3

    탑승 하고자 하는 배의 최대 수용 무게 15 < 17 (= 탑승하고자 하는 인원의 총 무게)이므로 7번째까지 탑승 불가

③ 3 ~ 6번째까지 탑승하는 경우

    탑승 인원 무게 psum[6] - psum[2] = 23 - 9 = 14 ← 3 + 2 + 3 + 6

    탑승 하고자 하는 배의 최대 수용 무게 15 > 14 (= 탑승하고자 하는 인원의 총 무게)이므로 6번째까지 탑승 인원

    3번째 사람부터 3~5번째 인원의 무게는 현재 보다 적은 인원을 탑승시키는 것이므로 탐색 종료

 

- 몇 번째 인원까지 가능한 건지 Upper Bound 이분 탐색 처리

- DFS 탐색시 (현재 남은 인원, 남은 배들의 최대 수용 무게 합, 현재 까지 탑승 인원의 마지막 순서) 인자 전달

---

#include <stdio.h>
int B, N, totalWeight;
int boat[10], visit[10];
int passenger[100000], psum[100001];
int ans = -1;
 
// Upper Bound 탐색
int findBound(int s, int pivot){
    int start = s, end = N;
    int bound = -1;
    while (start <= end){
        int mid = (start + end) / 2;
        int w = psum[mid] - psum[s];
        // 설정한 인원만큼 탑승하지 못하는 경우
        if (w > pivot)
            end = mid - 1;
        // 일치하는 경우
        else if (w == pivot)
            return mid;
        else{
            bound = mid;
            start = mid + 1;
        }
    }
    return bound;
}
 
void DFS(int remain, int totalWeight, int s){
    // 현재 출항하지 않은 배의 무게가 이미 구한 값(ans)보다 작은 경우
    if (totalWeight <= ans)
        return;
    // 모든 인원을 배에 태운 경우
    if (remain <= 0){
        // 출항하지 않은 배들의 수용 무게
        ans = totalWeight;
        return;
    }
    // 중복없는 순열
    for (int i = 0; i < B; i++){
        if (visit[i]) continue;
        int end = findBound(s, boat[i]);
        // 현재 배의 순서로 남은 인원을 한명도 태우지 못하는 경우
        if (end == -1) continue;
        visit[i] = 1;
        DFS(remain - (end - s), totalWeight - boat[i], end);
        visit[i] = 0;
    }
}
 
int main(void){
    scanf("%d %d", &B, &N);
    for (int i = 0; i < B; i++){
        scanf("%d", boat + i);
        totalWeight += boat[i];
    }
    for (int i = 0; i < N; i++){
        scanf("%d", passenger + i);
        psum[i + 1] = passenger[i] + psum[i];
    }
    // 수용할 수 있는 전체 무게보다 사람이 많은 경우
    if (psum[N] > totalWeight){
        printf("-1");
        return 0;
    }
    DFS(N, totalWeight, 0);
    printf("%d", ans);
}