【白俊】1092号船

ソース:https://www.acmicpc.net/problem/1092

に答える

クレーン単、箱単降順配列

クレーンごとに

個の移動可能な箱を格納

すべてのクレーンにおいて、移動する箱の中でまだ移動していない箱

3回繰り返して、全部移動するまで.

感想

個人が試した解答がタイムアウトし、検索した解答

を参考にしました

の答えとは違うのは

移動していない箱を探していたとき、箱全体を探していました.

正解は可能な重量の箱

しか検索していないからかもしれません.
エラーコード

def init():

    n = int(input(''))
    crane_list = list(map(int, input('').split(' ')))
    m = int(input(''))
    box_list = list(map(int, input('').split(' ')))

    return n, m, crane_list, box_list


def get_box_idx(crane_idx, box_idx, box_excluded):

    while box_idx < m:

        if not box_excluded[box_idx]:
            if crane_list[crane_idx] >= box_list[box_idx]:
                return box_idx

        box_idx += 1

    return -1

def get_time():

    if max(crane_list) < max(box_list):
        return -1

    crane_list.sort(reverse=True)
    box_list.sort(reverse=True)

    crane_excluded = [False] * n
    box_excluded = [False] * m

    count = 0

    while True:

        crane_idx = 0
        box_idx = -1

        finished = False

        while crane_idx < n and box_idx < m:

            box_idx = get_box_idx(crane_idx, box_idx+1, box_excluded)
            if crane_idx == 0 and box_idx < 0:
                finished = True
                break

            box_excluded[box_idx] = True
            count += 1

            crane_idx += 1

        if finished:
            break
    
    return count


n, m, crane_list, box_list = init()

result = get_time()

print(result)

正しいコード

def get_time():

    # 이동이 불가능할 경우
    if max(box_list) > max(crane_list):
        return -1

    # 내림차순으로 정렬
    crane_list.sort(reverse=True)
    box_list.sort(reverse=True)

    # 각 크레인 별 이동 가능 박스 저장
    crane_dict = dict()
    for i in range(n):
        for j in range(m):

            if crane_list[i] >= box_list[j]:
                if crane_list[i] not in crane_dict:
                    crane_dict[crane_list[i]] = []
                crane_dict[crane_list[i]].append(j)

    answer = 0
    move_count = 0
    moved = [False] * m

    # 모두 다 옮길 때까지 반복
    while move_count < m:

        answer += 1

        # 모든 크레인에 대해
        for i in range(n):
            if crane_list[i] in crane_dict:
                # 이동 가능한 박스 반복
                for j in crane_dict[crane_list[i]]:
                    if not moved[j]:
                        moved[j] = True
                        move_count += 1
                        break

    return answer


n = int(input(''))
crane_list = list(map(int, input('').split(' ')))
m = int(input(''))
box_list = list(map(int, input('').split(' ')))

result = get_time()

print(result)