[백준] 22988번 재활용 캠페인 (투포인터 문제)

사용 언어 - Python3

문제 -  22988번 재활용 캠페인

투포인터 : 가능성을 지워주는 방법

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

22988번: 재활용 캠페인

 

정답

(투포인터) 양쪽 끝에서 비교하면서 만나면 종료

두 병의 용량 반납 -> (A+B+X/2) 용량이 담긴 새로운 용기

s = 시작포인터 = 0

e = 끝포인터 = n-1 

cnt  = 채워진 용기 개수

remain = 짜투리 용기 개수

 

총 용량 13(x)일 때,

1. B가 13이면, 이미 채워져 있는 것이므로 cnt += 1, e-=1 continue

2. 두 용기의 합(A+B)이 6.5  이상이라면, 두 병을 제거하고 새로운 용기 받기 cnt += 1, e-=1, s+=1

3. 짜투리

두 수를 합했는데, 6.5를 넘지 않는다면, e를 아무리 줄여도 6.5를 넘지 않는다.

1 2 3 5

1+5  6.5 넘지 않음 => 1+3, 1+2도 모두 6.5 넘지 않음. 오름차순 정렬되어있기 때문

end 포인터는 그대로 두고 start만 올린다 e+= 1

1은 그냥 짜투리로 넣어준다. remain+= 1 

 

2+3 6.5 넘지 않음 => 2는 짜투리로 넣어준다. remain += 1 e+= 1

3에서 투포인터 만남.

투포인터가 만났다면, 그것도 아무것도 합해질 수 없으므로 짜투리로 넣어준다. remain+= 1

 

4. 짜투리 용기 처리

짜투리 용기가 3개라면, 용량이 무엇이던지

용기1 + 용기2 -> new 용기 + 용량 6.5

new 용기 + 용기3 -> new 용기 + 용량 13

짜투리 용기가 3개일 때마다 가득찬 용기는 1개 생성된다.

remain//3

 

n, x = map(int,input().split()) # 용기의 수, 용기의 총 용량
arr = sorted(list(map(int,input().split()))) # 각 병에 남아있는 용량

s = 0
e = n-1
remain = 0
cnt = 0

while s <= e: # s와 e가 교차되면 멈춘다
    if arr[e] == x:
        cnt += 1
        e -= 1
        continue
    
    if s == e:
        remain += 1 # 짜투리를 하나 추가한다.
        break
        
    if arr[s] + arr[e] >= (x/2):
        cnt += 1
        e -= 1
        s += 1
    else:
        remain += 1
        s += 1 # 수가 커진다.

print(cnt+remain//3)

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/22988_%EC%9E%AC%ED%99%9C%EC%9A%A9%EC%BA%A0%ED%8E%98%EC%9D%B8.py