백준 22988번 파이썬 문제풀이(재활용 캠페인)

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

22988번: 재활용 캠페인

 

---

이 문제는 문제의 풀이 해답을 잘 찾아야 한다. 우선 이미 X인 병은 제외시키고 해당 개수만큼 추가해준다. 그 후 2개를 들고가면 X / 2 만큼 절반을 주기 때문에 나머지 2병이 X / 2 보다 크거나 같은 2병을 찾는데 2중 반복문으로 찾으면 시간초과가 발생한다. 따라서 투 포인터로 찾을 수 있어야 하며 나머지 남은 병의 개수에서 3병을 들고가면 반드시 1병으로 교환 받을 수 있다. 이를 토대로 코드를 구성하면 된다.

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

array = list(map(int, input().split()))

array.sort()  # 투포인터 찾기위한 정렬
count = 0  # 개수를 셀 변수
count += array.count(X)  # 이미 X인것은 교체할 필요가 없으므로
for i in range(count):  # 그 개수 만큼
    array.pop()  # 리스트에서 빼준다.

s = 0  # 투포인터 시작인덱스
e = N - 1 - count  # 투포인터 끝인덱스(위에서 인덱스의 범위가 줄었으므로)
rest_count = N - count  # 남은 병 개수
while s < e:

    # 만약 두개의 병이 절반 이상이라면 2개의 병으로도 한개의 꽉찬 병을 만들 수 있으므로
    if array[s] + array[e] >= X / 2:
        count += 1  # 해당 병 2개를 꽉찬 용기로 교체한다.
        rest_count -= 2  # 병을 2개씩 빼준다.
        e -= 1  # 끝 인덱스를 한칸 앞으로 땡긴다.
        s += 1  # 시작 인덱스를 뒤로 한칸 민다.
    else:  # 만약 교환할 수 있는 양보다 적다면
        s += 1  # 시작 인덱스를 한칸 뒤로 민다.

print(count + rest_count // 3)  # 구한 개수와 남은 개수에서 3개씩 뽑아서 더해서 가면 된다.