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

그리디, 정렬, 투 포인터 / 실버 3

🐈

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

28353번: 고양이 카페

 

내 풀이

N, K = map(int, input().split())

cats = sorted(map(int, input().split()))
ans = 0

s = 0
e = N-1

while e-s > 0:
    if cats[s] + cats[e] > K: # 무게 초과
        e -= 1
    else:
        ans += 1
        s += 1
        e -= 1

print(ans)

투포인터로 풀었다.

 

처음에는 오름차순 정렬 후, 무게가 가장 적게 나가는 고양이를 두 마리씩을 더하는 방식을 생각했는데 잘못된 접근 방식이었다.

예를 들어, K = 10이고 고양이 6마리의 무게가 9 5 6 7 4 3 라고 가정할 때, 오름차순 정렬하면 3 4 5 6 7 9가 된다.

이때 무게가 가장 적게 나가는 고양이를 두 마리씩 더하면 (3+4) 이 한 쌍의 합만 10 이하이기 때문에 최대 한 명이 행복해질 수 있다는 답이 나온다. ((5+6)과 (7+9)는 10을 초과함)

그러나, (3+7), (4+6) 과 같이 조합하면 최대 두 명이 행복해질 수 있다.

 

따라서, 투 포인터를 사용하는 것이 올바르다.

s(시작 인덱스)를 가장 작은 값의 인덱스로 초기화하고, e(끝 인덱스)를 가장 큰 값의 인덱스로 초기화한다.

s = 0
e = N-1

 

두 인덱스는 겹치면 안 된다. (인덱스가 겹치는 경우는 같은 고양이를 가리키는 경우임)

e(끝 인덱스)가 s(시작 인덱스)보다 무조건 커야 하며, e-s의 값이 1 이상이 되어야 하므로,

while문은 e-s > 0일 때 반복되도록 한다.

while e-s > 0:

 

cats[s] + cats[e]가 K를 초과한 경우, 값을 줄여서 다시 비교해봐야 하므로, e(끝 인덱스)를 하나 줄인다.

if cats[s] + cats[e] > K: # 무게 초과
        e -= 1

 

cats[s] + cats[e]가 K 이하인 경우, ans(행복해질 수 있는 사람의 수)를 증가시키고, s와 e 모두 다음 인덱스로 이동시킨다.

else:
        ans += 1
        s += 1
        e -= 1