Skip to content

Latest commit

 

History

History
419 lines (313 loc) · 10.2 KB

1092.md

File metadata and controls

419 lines (313 loc) · 10.2 KB
Raw

Index

배

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

예제

입력 1

3
6 8 9
5
2 5 2 4 7

출력 1

2

입력 2

2
19 20
7
14 12 16 19 16 1 5

출력 2

4

입력 3

4
23 32 25 28
10
5 27 10 16 24 20 2 32 18 7

출력 3

3

입력 4

10
11 17 5 2 20 7 5 5 20 7
5
18 18 15 15 17

출력 4

2

권준혁

접근법 (생각의 흐름 설명)

매순간 크레인이 최대로 담을 수 있는 박스 수가 동적으로 바뀌지 않고 정해졌다 -> 그리디

상세한 해설

매 순간 최대로 담기 위해 내림차순 정렬:

    N = int(input())
    C = sorted(list(map(int, input().split())), reverse=True)
    M = int(input())
    B = sorted(list(map(int, input().split())), reverse=True)
  • 내림차순 정렬을 통해 무게 제한이 가장 큰 크레인부터 비교가 가능해진다.

박스 크기를 내림차순 정렬해서 저장한 리스트 B에서, 매순간 크레인이 최대한 담을 수 있는 박스의 위치는 위치가 일정한 규칙을 따르지 않기 때문에 직접 비교하면서 찾아야 한다.
비교를 통해 선택한 박스는 리스트 B에서 제거한다.
위 과정을 박스가 모두 사라질 때까지 반복한다.

        while(B):
            for i, n in enumerate(C):
                if B and n < B[-1]:
                    break
                for j, m in enumerate(B):
                    if n >= m:
                        del B[j]
                        break
            answer += 1
        print(answer)
  • B.pop(인덱스) 연산보다 del B[\인덱스] 연산이 더 빨랐다.
  • 최악의 경우: while문: logM번, 반복문: N * logM -> O(N * M*k) 이하는 보장함.

예외 케이스: 모든 박스를 배로 옮길 수 없는 경우:

    if max(C) < max(B):
        print(-1)
  • 가장 무거운 박스 크기가 무게 제한이 가장 높은 크레인의 무게보다 큰 경우이다.

회고

이번 문항은 주어진 테스트 케이스만으로는 반례를 찾기 어려웠다.
이번 문제는 다양한 반례를 통해 풀 수 있었다.

Solution

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())
    C = sorted(list(map(int, input().split())), reverse=True)
    M = int(input())
    B = sorted(list(map(int, input().split())), reverse=True)
    answer = 0
    if max(C) < max(B):
        print(-1)
    else:
        while(B):
            for i, n in enumerate(C):
                if B and n < B[-1]:
                    break
                for j, m in enumerate(B):
                    if n >= m:
                        del B[j]
                        break
            answer += 1
        print(answer)

안지완

접근법 (생각의 흐름 설명)

각 크레인이 자신이 들 수 있는 최대한 무거운 박스들을 옮긴다면, 옮기는 시간은 자연스럽게 최소가 될 것이라는 생각을 착안하여 구성했다.

따라서, 우선 크레인과 박스들을 내림차순으로 정렬을 한 후, 각 크레인마다 최대한 무거운 박스를 배정했다.

상세한 해설

n = int(input())
cranes = list(map(int, input().split()))
m = int(input())
boxes = list(map(int, input().split()))

# Tim Sort
cranes.sort(reverse=True)
boxes.sort(reverse=True)

Python에서는 기본 sort() 알고리즘이 Tim Sort 알고리즘을 채택하는 것으로 알려져있다.

Tim Sort는 Insertion Sort와 Merge Sort를 결합한 정렬 알고리즘으로, 인접한 메모리와의 비교를 이용한 Insertion Sort가 범위가 적으면 적을 수록 빠르다는 점을 이용하여, Merge Sort로 전체 데이터들을 분할한 다음, Insertion Sort로 이를 비교하는 기법이다.

따라서, O(nlogn * mlogm)의 시간 복잡도를 가지고 있다.

while boxes:
    for crane in cranes:
        for box in boxes:
            if crane >= box:
                boxes.remove(box)
                break
    ans += 1

이 부분에서는 크레인 별로 가장 무거운 박스를 배정받기 위해 다음과 같이 각 크레인 별로 가장 무거운 상자를 싣기 위해, 다음과 같이 조건문을 생성했다.

문제는, 이 경우 시간복잡도가 더욱 증가한다. boxes.remove(box)의 경우, 전체 배열을 스캔하여 가장 처음으로 나온 원소를 스캔한다. 즉, O(m)만큼의 시간복잡도가 증가한다.

따라서, 위의 loop은 결과적으로 O(nlogn * n) = O(n^2logn)만큼의 시간복잡도가 걸린다.

위의 문제는 이렇게 될 것이다. 반복문이 O(n*m)이므로,

O(n*m^2logm)이 될 것이다. 문제를 풀 긴 했으나, 상당히 시간이 걸리는 작업이다.

회고

좀 더 시간복잡도를 줄일 수 있는 방법을 찾으면 좋을 것 같다.

Solution

import sys

input = sys.stdin.readline

n = int(input())
cranes = list(map(int, input().split()))
m = int(input())
boxes = list(map(int, input().split()))

# Tim Sort
cranes.sort(reverse=True)
boxes.sort(reverse=True)

ans = 0

if boxes[0] > cranes[0]:
    print(-1)
    exit()

while boxes:
    for crane in cranes:
        for box in boxes:
            if crane >= box:
                boxes.remove(box)
                break
    ans += 1

print(ans)

오효근

접근법 (생각의 흐름 설명)

  • 동시에 이동
  • 최대 중량 정의

따라서 Greedy한 접근법으로 해결 가능 !

상세한 해설

입력 정의

import sys

read = sys.stdin.readline

N = int(read())
cranes = list(map(int, read().split()))
M = int(read())
boxs = list(map(int, read().split()))

Greedy 접근을 위한 sort

cranes.sort(reverse=True)
boxs.sort(reverse=True)

Greedy 구현

if boxs[0] > cranes[0]:
    print(-1)
else:
    time = 0
    while boxs:
        for crane in cranes:
            for box in boxs:
                if crane >= box:
                    boxs.remove(box)
                    break
        time += 1
    print(time)
  • 가장 큰 박스의 무게가 크레인 제한 보다 크면 -1 출력
  • 가장 큰 제한을 가진 크레인 부터 가장 무거운 박스를 옮김
  • 모든 박스가 옮겨질 때 까지 반복

회고

while loop를 생각해내기 어려울 수 있다.

Solution

import sys

read = sys.stdin.readline

N = int(read())
cranes = list(map(int, read().split()))
M = int(read())
boxs = list(map(int, read().split()))

cranes.sort(reverse=True)
boxs.sort(reverse=True)

if boxs[0] > cranes[0]:
    print(-1)
else:
    time = 0
    while boxs:
        for crane in cranes:
            for box in boxs:
                if crane >= box:
                    boxs.remove(box)
                    break
        time += 1
    print(time)

조은학

접근법 (생각의 흐름 설명)

  • 엄청 유명한 문제인듯?
  • c까지만 쳤는데 답을 다써줬다..?
  • 역순정렬하고..
  • 잘풀었다 생각했는데 계속해서 시간초과가 남

상세한 해설

  • 역순 정렬후에
  • 박스에서 적절한 것을 크레인에 실어주면된다.
4
23 32 25 28
10
5 27 10 16 24 20 2 32 18 7
32 32
28 27
25 24
23 20
32 18
28 16
25 10
23 7
32 5
28 2

회고

  • pypy로 하니까 통과한다
  • python 으로 시간초과 안난 분 계신가요..??

Solution

n = int(input())
crane = list(map(int, input().split()))
m = int(input())
box = list(map(int, input().split()))

crane.sort(reverse=True)
box.sort(reverse=True)

if crane[0] < box[0]:
    print(-1)
    
else:
    ans = 0
    while box:
        ans += 1
        for i in crane:
            for j in range(len(box)):
                if i >= box[j]:
                    box.pop(j)
                    break
    print(ans)