처음 생각한 풀이

• crane리스트와 jim리스트를 내림차순으로 정렬한다.
• crane의 최댓값과 jim의 최댓값을 비교 -> 만약 crane[0]<jim[0] 이면 반복문 break, cnt++

바뀐 풀이

질문게시판의 반례를 보고 틀린 부분을 고쳤다

------------------------- # 반례 1 -----------------------
입력
4
1 2 3 4
8
1 1 2 2 3 3 4 4
    
올바른 출력
2

이 코드의 출력
4
------------------------- # 반례 2 -----------------------
3
10 6 5
11
6 8 9 6 8 6 9 6 8 6 9

올바른 출력
6

이 코드의 출력
8
---------------------------------------------------------

반례2의 상황을 이해하며 코드를 수정했다.

• 나의 기존 풀이는 남아있는 crane과 jim 리스트의 값들 중 최댓값끼리만 비교하였고, 만약 crane의 최댓값이 jim의 최댓값보다 작다면 cnt+=1 을 한 뒤에 다시 다음턴으로 넘어가는 로직이었다. -> 이 로직은 그리디 알고리즘을 완벽히 무시한 풀이ㅠㅠ

• 그리디 알고리즘을 생각해보면, 미래는 생각하지 않고 현재 상황에서 지금 당장 좋은 것만 고르는 방법
  == 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법

-> 나중은 생각하지 않고 한 턴에 최대한 많은 크레인을 사용하여 최대한 많은 짐을 옮겨야 한다!!

정답 코드

• Python 3로 제출하면 시간초과가 뜨지만 Pypy3로 제출하면 정답이다,, Whyrano,,whyrano,,

# 그리디 알고리즘 - 1092번 - 배
import sys, heapq
input = sys.stdin.readline
N = int(input())
crane = list(map(int, input().split()))
K = int(input())
jim = list(map(int, input().split()))
crane.sort(reverse=True)
jim.sort(reverse=True)
cnt=0

if crane[0] < jim[0]:
    print("-1")
else:
    while jim:
        tmp = crane[:]
        # print(tmp)	# 찍어보며 검증하는 부분
        # print(jim)
        i=0
        while tmp and len(jim)>i:
            if tmp[0] >= jim[i]:
                del tmp[0]
                del jim[i]
            else:
                i += 1
        cnt += 1
    print(cnt)

후기

그리디 알고리즘이 언제 사용되는지 정확하게 파악하며 문제에 접근하는 연습을 해야겠다!!!