1092

날짜 : 2022. 11. 28

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())  # 크레인의 개수
c = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())  # 박스의 수
box = list(map(int, sys.stdin.readline().split()))
c.sort(reverse=True)
box.sort(reverse=True)
cnt = 0

if c[0] < box[0] : print(-1)
else:
    cnt = 0
    while box:
        cnt += 1
        i = 0  # i : 크레인 인덱스
        while i < len(c):
            if not len(box): break # 다 뺀 경우
            if c[i] >= box[0]:  # 뺄 수 있는 경우
                #print(box[0], end=" ")
                del box[0]  # 뺌
            else:
                for j in range(len(box)):
                    if c[i] >= box[j]: # 뺄 수 있는 경우
                        #print(box[j], end=" ")
                        del box[j]
                        break
            i += 1
    print(cnt)

 

 

풀이

- 크레인과 박스 크기를 내림차순으로 정렬

- 각 박스와 크레인 크기를 비교하면서 크레인의 크기가 박스의 크기보다 크다면 1번째 박스(제일 큰 박스) 삭제

- 만약 작다면 다음 크레인으로 이동하면서 삭제

- 마지막 크레인으로 이동 후 옮길 수 없거나 크레인을 모두 사용한 경우 cnt 증가 후 다시 초기화한다.

- 이를 반복하여 문제를 풀이

 

 

알게된 점

- 처음 오름차순으로 정렬 후 문제를 풀었지만 오답이 나왔다.

반례)

3
6 8 9
9
1 2 3 4 5 6 7 8 9

 

- 오름차순으로 정렬한 경우 아웃풋은 4가 나오지만 실제 정답은 3이다.

- 그래서 내림차순으로 정렬했고 이후 뽑아내기 전 cnt에 따른 박스 값들을 출력해서 하나씩 체크했다.

 

 

 

참고 사이트

-