[백준 1092번] 배(파이썬)

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

1092번: 배

그리디 알고리즘을 풀 때마다 느끼지만

혼자 쉐도우 복싱 오지게 하다가

힌트를 보면 현타가 많이 옵니다...하...

 

우선, 저는 예시는 통과했는데

제출해보니 오답이라고 떴습니다.

그래서 방법을 어떻게 바꿀까하다가

고민을 상당히 많이 했고

힌트를 보다가 이렇게 하면 되겠구나 라는 감이 왔습니다.

 

첫 번째로, 크레인과 박스를 정렬해줍니다.

이건 모든 그리디 알고리즘의 기본.

대체적으로 뭔가 많이 주어져있을 때

'순서대로'하는 게 아니라면

정렬을 하면 반은 먹고 들어가니

정렬 꼭 해줍니다.

특히 파이썬은 sort한번이면 정렬이 다 되니깐

제발 제발 해줍니다.

 

그 다음은 박스를 어떻게 제거할까입니다.

우선, 크래인이 모두 동시에 사용할 수 있으므로

크래인을 동시에 사용하도록 만듭니다.

그리고 크래인이 들 수 있는 박스를 만나면

크래인을 쓰는 걸로 만들어줍니다.

 

#백준 1092번 배

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 box[0]>crane[0]:
    print(-1)
else:
    answer=0
    while box:
        for i in range(N):
            #각 크래인마다, 들 수 있는 박스가 뭐있는지 살펴본다
            for j in range(len(box)):
                #들 수 있는 박스를 발견하면 옮겨준다
                if crane[i]>=box[j]:
                    del box[j]
                    break

        #crane을 다 돌았으면 time이 하나 상승한다는 개념
        answer+=1

    print(answer)

pypy3로 통과했습니다.

 

내가 생각했던 뻘짓들

 

1. 어떤 box도 들지 못하는 crane은 계속 제거?

-->반복문을 돌 때마다

다 체크를 해줘야하므로 

시간초과가 당연하게 발생할듯.

 

2. 만약에 크래인을 다 돌려도 박스를 못뺴는 게 있다면

-1을 출력할까?

-->어처피 내림차순으로 정렬했다.

박스의 가장 큰 게 크래인 가장 큰 것보다 크면

어떻게 크래인을 써도 들지를 못한다.

반면, 그렇지 않은 경우에는

어떻게든 옮겨서 치울 수 있으므로 가능하다.

 

그리디는 많이 풀어봐야한다는 말이 맞네요.

경험치가 늘어나야지 아이디어도 자연스럽게 떠오를 것 같습니다.