[Algorithm🧬] 정올 2720 : 여객선

문제

시간 초과.

배, 사람을 순서대로 태우는데
사람을 한 배에 태울 수 있으면 계속 태우고, 태울 수 없는 순간이 오면 다음 배로 넘어갔다.
근데 그러면 이제 배를 어떤 순서로 남기냐에 따라서 남은 배의 최대 수용 무게가 달라져서..
시간초과일 것 같다~ 라고 생각하면서 permutation 돌림..

개선하려고 다시 생각해보니,
타려는 사람이 전부 6 넘고 최대 용량이 3인 배가 ships 중간에 있어.. 그러면 3인 배는 카운트가 안되고 있음...

import sys
from itertools import permutations
readl = sys.stdin.readline

def DFS(level, idx):
    global max_sum
    
    if idx >= B:
        # max_sum = -1
        return
    
    if level >= N:
        # print(ships)
        if idx < B - 1:
            max_sum = max(max_sum, sum(ships[idx + 1:B]))
        return
    
    # print(level, idx, weights[level], ships[idx])

    
    if ships[idx] - weights[level] >= 0:
        ships[idx] -= weights[level]
        DFS(level + 1, idx)
        ships[idx] += weights[level]
    else:
        DFS(level, idx + 1)
    


B, N = map(int, readl().split())
ships = [int(readl()) for _ in range(B)]
weights = [int(readl()) for _ in range(N)]
# ships.sort(key=lambda x:-x)

if sum(weights) > sum(ships):
    print(-1)
    exit(0)


max_sum = 0
for arr in permutations(ships, B):
    ships = list(arr)
    DFS(0, 0)
print(max_sum)

개선

permutation(ships, B) 에서 어떤 경우를 제외할 수 있는지.. 모르겠어서
https://zoosso.tistory.com/505 를 참고하여 풀었다.

DFS 자체를 승객을 하나하나 태워서 이용하는게 아니라 부분합을 이용해서 이번 배에 몇번째 사람까지 태울 수 있는지를 판단하고 (그 판단도 이진 탐색으로 횟수 줄이고) 하는 거였음... 이걸 어떻게 생각함...

import sys
sys.setrecursionlimit(10**6)
readl = sys.stdin.readline

# 배에 몇번째부터 몇번째까지 가능한지 탐색.
def findPeople(s, pivot):
    start = s
    end = N
    sol = -1
    while start <= end:
        mid = (start + end) // 2

        w = psum[mid] - psum[s]
        if w > pivot:
            end = mid - 1
        elif w == pivot:
            return mid
        else:
            start = mid + 1
            sol = mid
    return sol

def DFS(level, totalShip, s):
    global max_remain

    if totalShip <= max_remain:
        return
    
    if level >= N:
        # print(max_remain)
        max_remain = totalShip
        return
    
    # 배를 기준으로 1번 배, 2번 배, 3번 배 각각에서 가지를 뻗어봄.
    # ch 이용해서 한번 탄 배에 다시 타진 않도록.
    for i in range(B):
        if ch[i]: 
            continue
        end = findPeople(s, ships[i])
        if end == -1: 
            continue
        
        ch[i] = 1
        DFS(level + (end - s), totalShip - ships[i], end)
        ch[i] = 0



B, N = map(int, readl().split())
ships = [int(readl()) for _ in range(B)]
weights = [int(readl()) for _ in range(N)]
psum = [0] * (N + 1)
ch = [0] * B

for i, w in enumerate(weights):
    psum[i + 1] = psum[i] + w

if psum[N] > sum(ships):
    print(-1)
    exit(0)

max_remain = -1
DFS(0, sum(ships), 0)
print(max_remain)

대회답