[BOJ 22988, Python 3] 재활용 캠페인

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

22988번: 재활용 캠페인

 

 

풀이

X ml인 헤어 에센스를 최대한 많이 만들어야 하므로 일단 2개로 1개를 만드는 것을 생각할 수 있습니다.

이러면 투포인터를 사용해 a = 0, b = len(C) - 1로 설정하여 C[a] + C[b] >= 0.5 * X가 되면 답에 1을 추가해줍니다. 그리디적인 아이디어인데 [남은 용량이 제일 작은 것들을 해치우는 것이 우선 순위이다] -> [남은 용량이 큰 것과 합쳐서 없애준다] 순으로 생각하면 좋을 것 같습니다.

 

이제 남는 헤어에센스들이 있는데, 헤어에센스를 2개를 합칠 때마다 전체 용량의 반절을 채워주므로 무조건 3개가 되면 용량이 꽉 찬 헤어에센스를 만들 수 밖에 없습니다.

그리고 남는 헤어 에센스들중에 서로 다른 2개를 선택해도 X ml인 헤어 에센스를 만들 수 없는 것이 보장되어 있으므로 무조건 3개를 사용할 수 밖에 없습니다.

 

참고로 C의 값은 정렬되어 있지 않은 값이 주어지므로 정렬해주고, C[i] = X인 경우도 있으므로 이 경우는 답에 1을 더해줘야합니다.

 

 

그래서 정답은 (원래 X ml인 헤어 에센스 개수) + (투 포인터를 이용하여 헤어 에센스 2개로 만든 X ml 헤어 에센스 개수) + (나머지 헤어 에센스의 수 // 3)를 해주면 됩니다.

 

 

코드

n, x = map(int, input().split())
C = sorted([*map(int, input().split())])
ans = 0
for i in range(n-1, -1, -1):
    if C[i] == x: C.pop(); ans += 1
    else: break
s, e = 0, len(C) - 1
etc = 0
while s <= e:
    if s == e: etc += 1; break
    if 2 * (C[s] + C[e]) >= x:
        s += 1
        e -= 1
        ans += 1
    else:
        etc += 1
        s += 1
print(ans + etc // 3)