[백준 #22988] 재활용 캠페인 - Python

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

22988번: 재활용 캠페인

---

---

이 문제에서 사용된 알고리즘은 투포인터인데, 말 그대로 포인터를 두 개를 사용하여 문제를 해결하는 것이다.

 

핵심은 포인터 두 개를 적절하게 활용하여, 정답이 될 수 있는 범위를 좁혀 나아가는 것이다.

투포인터를 예를 들어 설명하자면 다음과 같다.

---

[투포인터 이해를 위한 예시]

다음과 같은 정렬된 배열에서 두 수의 합이 12가 되는 두 수를 찾고 싶다고 하자

이 때 배열의 양 끝에 포인터를 두자.

각 포인터에서의 수는 1과 10이다.

1+10 = 11이므로, 목표로 하는 수인 12 보다 작다.

 

따라서 1을 이용해서는 12를 만들 수 없다.

→→ 1을 가르키는 포인터를 우측으로 이동시켜 탐색의 범위를 좁힌다.

이번에는 포인터가 3과 10을 가르키고 있다.

3+10 = 13이므로, 목표로 하는 수인 12 보다 크다.

 

따라서 10을 이용해서는 12를 만들 수 없다.

→→ 10을 가르키는 포인터를 좌측으로 이동시켜 탐색의 범위를 좁힌다.

이번에는 포인터가 3과 9를 가르키고 있다.

3+9 = 12이므로, 목표에 도달하였다.

 

위 예시처럼 투포인터의 핵심은 정답의 범위를 좁힌다는 것이다.

---

그럼 이제 투포인트를 이용해 본격적으로 이 문제를 풀어보자.

문제가 살짝 복잡하기 때문에, 가능한 경우의 수를 나눌 필요가 있다.
온전한 1병의 헤어에센스를 얻기 위한 경우의 수는 다음과 같다.

1. 가지고 있던 에센스가 처음부터 온전한 1병이었다.
2. 서로 다른 두 병을 합쳐서 온전한 1병으로 만들 수 있다.
3. 서로 다른 두 병을 합쳐도 온전한 1병으로 만들 수 없다.

1번째 경우에는 그냥 결과에 1을 더하면 된다.

2번째 경우가 되기 위해서는 두 병에 담긴 에센스 용량의 합이 (X / 2) 이상이 되어야 한다.

1번째, 2번째 경우에 모두 포함되지 못한 병은 3번째 경우에 해당하게 되고, 이 때는 3병을 합치면 온전한 1병을 만들 수 있다.

 

언뜻 보면 투포인트가 사용될 여지가 없어보이지만, 우리는 최대한 많은 온전한 헤어에센스를 얻고 싶다.

따라서 2번째 경우에 들어가는 쌍을 만들 때, 두 용량의 합이 (X / 2) 보다 큰 최소한의 수가 되도록 만들 필요가 있다.

투포인트를 적용시키면 두 용량의 합이 (X / 2) 보다 크게 되는 쌍의 범위를 좁혀 나아감으로써, 조건을 만족하는 최소한의 합을 갖는 쌍을 만들어낼 수 있고, 이를 통해 최대한 많은 온전한 에센스를 얻어낼 수 있다.

 

위와 같은 내용을 코드로 구현하면 아래와 같다.

n,x = map(int, input().split())
arr = list(map(int, input().split()))

"""
가능한 경우의 수

1. 남은 용량이 x인 경우
그냥 count += 1

2. 두개를 합쳐서 남은 용량이 x/2 이상인 경우
두개를 합쳐서 count += 1

3. 위 두 경우를 제거하고 남은 병들은 뭘 해도 두 개로 한 병을 만들 수 없다.
3개를 합치는 경우 무조건 1개를 만들 수 있음
예를 들어, 가장 작은 0ml, 0ml, 0ml라고 해도
{(0 + 0 + 2/x) + 0 + 2/x} = x 이므로 
3개를 합쳐서 count += 1
"""

#투포인터 활용을 위한 정렬
arr.sort()

lower=0
upper = n-1

count = 0   #온전한 병의 개수
rest = 0    #3개를 합쳐야되는 것들

while lower<=upper:
    #이미 온전한 병이라면 그냥 둔다.
    if arr[upper] == x:
        count +=1
        upper-=1
    #병이 하나만 남았다면, 쌍을 이룰 수 없다.
    elif lower == upper:
        rest += 1
        break
    #두 용량을 합쳤을 때, (x/2)보다 크다면 두 병을 합치면 온전한 1병이 된다.
    elif (arr[lower] + arr[upper]) >= (x/2):
        count +=1
        lower+=1
        upper-=1
    #두 용량을 합쳤을 때, (x/2)보다 작다면 3병을 합쳐야 온전한 1병이 될 수 있다.
    else:
        lower+=1
        rest+=1

#2병을 합쳐서 온전한 1병을 만들지 못한 병들은, 3병씩 합쳐서 온전한 1병을 만든다.
count += (rest//3)

print(count)