BOJ 1092 : 배 (Python)

문제

https://www.acmicpc.net/problem/1092

1092번: 배

 

 

코드

import sys

n = int(sys.stdin.readline()) #크레인 수
limit = [[0 for i in range(2)] for j in range(n)] #각 크레인의 무게 제한을 0열에, 각 크레인이 이동시킨 박스의 수를 1열에 넣는 배열

array = list(map(int, sys.stdin.readline().split())) #크레인의 무게 제한

for i in range(n):
    limit[i][0] = array[i]
    
limit.sort(reverse = True) #limit 배열을 내림차 순으로 정렬

m = int(sys.stdin.readline()) #상자 수
weight = list(map(int, sys.stdin.readline().split()))
weight.sort(reverse = True) #weight 배열을 내림차 순으로 정렬

i = 0
q = 0
for i in range(m-1):
    limit.sort(reverse = True)
    if weight[i] <= limit[(i+n-q)%n][0]: #상자의 무게가 크레인의 무게 제한보다 작다면
        limit[(i+n-q)%n][1] += 1 #크레인으로 상자를 이동
    else:
        for j in range((q+n)%n,(i+n-q)%n): #가능한 왼쪽 크레인부터 다시 매칭 시작
            if weight[i] <=limit[j][0]: #상자의 무게가 크레인의 무게 제한보다 작다면
                limit[j][1] += 1 #크레인으로 상자를 이동
                q+=1 # 다시 else문에 들어왔을 때 가능한 왼쪽 인덱스를 오른쪽으로 한 칸 미루기 위해 넣음
                break

if limit[limit.index(max(limit,key = lambda x:x[1]))][1] == 0: #1열을 기준으로 가장 큰 값
    print(-1)
else:
    print(limit[limit.index(max(limit,key = lambda x:x[1]))][1])

 

 

풀이

크레인과 박스들을 내림차 순으로 정렬한 뒤에 왼쪽부터 차례대로 크레인에 박스를 하나씩 매칭시킨다.

 

ex)

3
6 8 9
5
2 5 2 4 7

위와 같이 입력을 받았다면

 

크레인은 9 8 6

박스는 7 5 4 2 2

 

9	8	6
7	5	4

하나씩 매칭을 시키다가 마지막 인덱스에 도달하면 다시 0번 인덱스부터 시작해서 매칭시킨다.

 

9	8	7
7	5	4
2	2

한 크레인이 가진 원소들의 개수가 최대 2개이므로 답은 2가 된다. 

 

만약 매칭 중에 크레인의 무게 제한보다 박스의 무게가 더 큰 경우에는 가능한 가장 왼쪽에서부터 다시 매칭을 시작한다.

else:
        for j in range((q+n)%n,(i+n-q)%n):
            if weight[i] <=limit[j][0]:
                limit[j][1] += 1
                q+=1
                break

 

 

반례... 오류...

4
4 3 2 1
8
1 1 2 2 3 3 4 4

위와 같이 주어지는 경우에 올바른 값은 2인데 마지막 1이 가장 마지막의 인덱스에 들어가지 않고 다시 왼쪽에서부터 매칭을 시작해서 3으로 잘 못 나온다...

 

 

 

올바른 풀이

크레인과 박스들을 내림차 순으로 정렬한다.

박스가 남지 않을 때까지 아래의 과정을 반복한다.

크레인에 담을 수 있는 가장 큰 박스를 담고 다음 크레인으로 넘어가서 다시 또 크레인에 담을 수 있는 가장 큰 박스를 담고.... x 무한반복

→크레인에 담은 박스는 박스 리스트에서 제거한다.