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

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

 

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

 

 

문제풀이1-List

import sys
sys.stdin=open("input.txt", "r")

n, limit= map(int, input().split())  #

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

#일단 오름차순으로 몸무게를 정렬한다.
p.sort()
cnt=0

while p:            #p리스트가 비어있다면 False가 된다.!!!
  if len(p)==1:     #마지막 한명이 남은 경우 혼자 타고 나간다. 이 처리를 해주지 않는 경우 에러발생
     cnt+=1
  if p[0] + p[-1] > limit:
    p.pop(-1)       #-1은 맨 뒤쪽에 있는 요소를 의미함
    cnt +=1
  

  else:
    p.pop(0)
    p.pop(-1)
    cnt +=1

print(cnt)

 

 

 

문제풀이2 -deque

import sys
from collection 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:            #p리스트가 비어있다면 False가 된다.!!!
  if len(p)==1:     #마지막 한명이 남은 경우 혼자 타고 나간다. 이 처리를 해주지 않는 경우 에러발생
     cnt+=1
  if p[0] + p[-1] > limit:
    p.pop(-1)       #-1은 맨 뒤쪽에 있는 요소를 의미함
    cnt +=1
  

  else:
    p.popleft()     #맨 앞쪽에 있는 요소를 뺀다.
    p.pop(-1)
    cnt +=1

print(cnt)

 

Hint

1. 오름차순 정렬 후 몸무게가 가장 적게 나가는 사람과 몸무게가 가장 많이 나가는 사람을 비교
2. 조건에 부합하는 경우 몸무게가 가장 많이 나가는 사람과 적게 나가는 사람이 이 함께 타고 나간다.
3. over되는 경우 몸무게 많은 사람 혼자 타고 나간다.
4. 몸무게 가장 적게 나가는 사람과 두번째로 몸무게가 많이 나가는 사람을 비교한다.
5. 반복