[BOJ] 백준 28353 고양이카페 Python

import sys
import math
input = sys.stdin.readline

N, K = map(int,input().split())
A = list(map(int,input().split()))
n = len(A)

A.sort(reverse=True)

cnt = 0

for a in A:
    m = A.index(a)
    A.remove(a)
    A.insert(m,K)
    for b in A:
        if a + b <= K:
            l = A.index(b)
            A.remove(b)
            A.insert(l,K)
            cnt += 1
            break
        else:
            continue
print(cnt)

Pypy God의 힘을 믿어야 하는 수 밖에 ...

결론적으로 알고리즘으로는,

먼저 큰 순서대로 정렬을 시킨다.

예를 들어, [22,1,20,8,5,3] 으로 고양이들의 무게들이 주어지고,
친구들이 버틸 수 있는 최대 몸무게가 25라고 하자.

이때 무게들을 무거운 순으로 정렬

-> [22,20,8,5,3,1] 앞에서부터 25를 넘지 않게끔 다른 한 마리의 고양이를 선택

-> 고양이의 무게로서 3kg , 1kg가 가능하지만 이때는 3kg을 취한다.
이때, 22kg , 3kg의 고양이를 배제하는 방법으로서, 두 마리의 무게를 25kg으로 두고 cnt를 +1 시켜주자. (계산에서 pass 시키기 위하여)

-> [25,20,7,5,25,1] 이 새로운 고양이의 무게 리스트가 된다.

-> 20kg의 고양이에 대해서, 25kg이 되지 않게끔 하는 제일 무거운 고양이는 5kg짜리이다. 동일하게 이 두마리를 25kg으로 해주고, cnt를 1 올려준다.

-> [25,25,7,25,25,1]이 새로운 고양이의 무게 리스트가 되고, 동일하게 7kg의 고양이에 대해서도 같은 작업을 반복하면, cnt을 1 올려주면서 리스트는 [25,25,25,25,25,25]가 되고 계산 종료.

(홀수마리의 고양이에 대해서는 홀수 마리가 남게 되는 것은 자명하다.)

 

Pypy God은 통과시켜주시는데 Python님은 영 아니라고 하시는 것 같더라. 젠장...

결론적으로 그리디 알고리즘이 아닐까 싶습니다.