백준 17799 : Feeding Seals (Python)

본문 링크

import sys
input=sys.stdin.readline

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

L=sorted(list(map(int,input().split())))

if N==1:
    print(1)
else:
    start = 0 ; end = N-1 ; count = 0
    while start<=end: # buckets을 하나만 쓸수 있으므로 start<=end로 잡아준다.
        if L[start]+L[end]<=C:
            count+=1
            start+=1
            end-=1
        elif L[start]+L[end]>C:
            count+=1
            end-=1
    print(count)

📌 어떻게 문제에 접근할 것인가?

문제에서 $N,C$ 가 주어진다. $N$ 은 배열의 길이 $C$ 는 한사람이 최대 나를수있는 크기이다.
단 한번에 최소 1개부터 최대 2개를 운반할수있다.

예제 입출력을 보자.

• 입력
  4 100
  44 35 66 67
• 출력
  3

(35+44) , 66 , 67 총 3번의 횟수가 필요하다.

그럼 가장 작은 횟수는 어떻게 구할것인가?

2개를 한번에 운반할수있는 경우를 최대한 많이 찾는것이다.

두 수의 합을 구하는 문제이기 때문에 투 포인터 알고리즘을 사용하였다.

📌 어떻게 투 포인터를 사용할 것인가?

먼저 배열의 최소값과 최대값을 더한다. 만약 이 합이 $C$ 보다 크다면
최대값은 무조건 1개만으로 운반해야하므로 count 를 1 증가시킨다.
그리고 end 값을 감소 시킨다.
이렇게 start 값과 end 값의 합이 $C$ 보다 작을때까지 계속 찾는다.
만약 합이 $C$ 보다 작으면 count 를 1 증가시키고 start+=1 와 end-=1 을 동시에 해준다.

✅ 코드에서 중요한 부분

• while 문의 조건은 start<=end 로 해준다. 한번에 1개를 운반할 경우가 존재하기 때문이다.
• 최대값과 최소값의 합이 $C$ 보다 작으면 start 와 end 를 동시에 움직여준다.
• $N$==1일때는 1 을 출력한다.
• 리스트 $L$ 은 정렬해준다.