[ BOJ / Python ] 1092번 배

7032 단어 bojpythongreedyboj

이번 문제는 크레인의 무게 제한과 상자의 무게를 내림차순 정렬한 뒤에 크레인과 상자를 가장 앞에서부터 검사하며 무거운 상자부터 무거운 크레인으로 옮기도록 배정해주고 크레인에 상자를 올릴 때마다 시간을 증가시키는 방식으로 해결하였다.

  • n을 입력받는다.
  • 크레인의 제한 무게를 입력 받을 crane 배열을 선언하고 입력받는다.
  • m을 입력받는다.
  • 상자의 무게를 입력 받을 box 배열을 선언하고 입력받는다.
  • crane과 box를 내림차순 정렬한다.
  • 옮겨진 상자의 갯수를 카운팅할 변수 cnt를 0으로 정의한다.
  • 상자를 옮기는 시간을 저장할 변수 time을 0으로 정의한다.
  • 상자가 옮겨짐을 표시하기 위한 배열 chk를 m개의 False로 구성되도록 정의한다.
  • 상자의 인덱스를 편하게 사용하기 위한 배열 tmp를 n개의 0으로 구성되도록 정의한다.
  • 만약 crane[0]이 box[0]보다 작을 경우 -1을 출력한 뒤에 프로그램을 종료한다.
  • cnt가 box 배열의 길이보다 작을 동안 반복하는 while문을 돌린다.
    -> n번 반복하는 i에 대한 for문을 돌린다.
    --> tmp[i]가 box 배열의 길이보다 작을 동안 반복하는 while문을 돌린다.
    ---> 만약 chk[tmp[i]]가 False이고, crane[i]가 box[tmp[i]]보다 크거나 같을 경우, (현재 상자가 안옮겨졌고 현재 크레인으로 옮길 수 있는 경우)
    ----> chk[tmp[i]]를 True로 갱신하고, tmp[i]를 1 증가시키고 cnt를 1 증가시킨 뒤 while문을 종료한다.
    ---> tmp[i]를 1 증가시킨다.
    -> time을 1 증가시킨다.
  • time을 출력한다.

Code

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)
cnt=0
time=0
chk=[False]*m
tmp=[0]*n
if crane[0]<box[0]:
    print(-1)
    quit()
while cnt<len(box):
    for i in range(n):
        while tmp[i]<len(box):
            if chk[tmp[i]]==False and crane[i]>=box[tmp[i]]:
                chk[tmp[i]]=True
                tmp[i]+=1
                cnt+=1
                break
            tmp[i]+=1
    time+=1
print(time)

좋은 웹페이지 즐겨찾기