[이진탐색] - 침몰하는 타이타닉(그리디)

 

침몰하는 타이타닉(그리디)

 

유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다.

유람선에는 N명의 승객이 타고 있습니다.

구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있 으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다.
N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요.

 

▣ 입력설명
첫째 줄에 자연수 N(5<=N<=1000)과 M(70<=M<=250)이 주어집니다.
두 번째 줄에 N개로 구성된 몸무게 수열이 주어집니다. 몸무게는 50이상 150이하입니다. 각 승객의 몸무게는 M을 넘지는 않습니다.

즉 탈출을 못하는 경우는 없습니다.

▣ 출력설명
첫째 줄에 구명보트의 최소 개수를 출력합니다.

 

▣ 입력예제 1
5 140
90 50 70 100 60

▣ 출력예제 1

3

 

나의 코드

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

cnt=0
l=0
r=len(arr)-1

while arr:
    if len(arr)==1:
        cnt+=1
        arr.pop()
    elif arr[l]+arr[r] >m:
        r=r-1
    elif arr[l] + arr[r]<=m:
        arr.pop(l)
        arr.pop(r)
        l=0
        r=len(arr)-1
        cnt+=1
    
print(cnt)

 

스택과 투포인터를 사용하였다.

사람들의 몸무게를 정렬한 뒤 투포인터로 양끝을 가리킨채 탐색을 시작한다.

양끝사람들의 무게 합이 제한 보다 큰 경우 가장 오른쪽 포인터를 한칸 이동하고

작거나 같은경우 양끝을 스택에서 제거한뒤 포인터를 조정하고 카운팅을 했다.

 

+ 근데 정답코드를 보니 위 나의 코드는 는 스택을 사용해서 큐처럼 사용을 했네..ㅇㅅㅇ

 

 

정답 코드

import sys
from collections import deque
sys.stdin=open("input.txt", "r")
n, limit=map(int, input().split())
p=list(map(int, input().split()))
p.sort()
p=deque(p)
cnt=0
while p:
    if len(p)==1:
        cnt+=1
        break
    if p[0]+p[-1]>limit:
        p.pop()
        cnt+=1
    else:
        p.popleft()
        p.pop()
        cnt+=1
print(cnt)

 

정답코드 큐를 사용해서 나와 같은 로직이지만 더 짧은 코드로 구현