[프로그래머스] Lv2. 완전범죄

문제 설명
A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다.
단, 각 도둑이 물건을 훔칠 때 남기는 흔적이 누적되면 경찰에 붙잡히기 때문에, 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.

물건을 훔칠 때 조건은 아래와 같습니다.
물건 i를 훔칠 때,A도둑이 훔치면 info[i][0]개의 A에 대한 흔적을 남깁니다.B도둑이 훔치면 info[i][1]개의 B에 대한 흔적을 남깁니다.
각 물건에 대해 A도둑과 B도둑이 남기는 흔적의 개수는 1 이상 3 이하입니다.

경찰에 붙잡히는 조건은 아래와 같습니다.
A도둑은 자신이 남긴 흔적의 누적 개수가 n개 이상이면 경찰에 붙잡힙니다.B도둑은 자신이 남긴 흔적의 누적 개수가 m개 이상이면 경찰에 붙잡힙니다.

각 물건을 훔칠 때 생기는 흔적에 대한 정보를 담은 2차원 정수 배열 info, A도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 n, B도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 m이 매개변수로 주어집니다.

두 도둑 모두 경찰에 붙잡히지 않도록 모든 물건을 훔쳤을 때, A도둑이 남긴 흔적의 누적 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
만약 어떠한 방법으로도 두 도둑 모두 경찰에 붙잡히지 않게 할 수 없다면 -1을 return해 주세요.

 

정답 코드

def solution(info, n, m):
    total_n = 0
    total_m = 0
    
    info = sorted(info, key = lambda x: [x[0] - x[1], x[1]], reverse = True)
    for itemInfo in info:
        if(total_m + itemInfo[1] < m):
            total_m += itemInfo[1]
            continue;
        total_n += itemInfo[0]
                
    if(total_n < n and total_m < m):
        return total_n
    
    return -1

 

A의 흔적을 최소화하면서도 B가 m 이상이 되지 않게 하려고 했다.

• info를 A의 흔적 - B의 흔적을 기준으로 내림차순 정렬
  • A가 도둑질할 때 B보다 더 많은 흔적 차이가 발생하는 아이템을 우선 고려했다.
  • 즉, A가 가져가면 손해인 것을 B가 가능하면 먼저 가져가도록 했다. 
• 동일하면 B의 흔적이 큰  순으로 정렬한다.
  • 흔적이 동일할 경우, B가 먼저  가져가도록 하여 A의 흔적을 최소화하도록 했다.