문제: https://school.programmers.co.kr/learn/courses/30/lessons/42885
유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 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
두명만 뽑으면 되니
오름차순 정렬을 해서 가장 무거운 사람이랑 가장 가벼운 사람이랑 짝을 해서
구명보트의 최소 개수를 구하는 것이 합리적여보인다.
만약 둘이 짝을 지었을때 몸무게가 초과 되면 가장 무거운 사람을 혼자 보내버린다.
만약 사람들이 홀수여서 짝이 안생기고 홀로 남는 경우 그대로 보내버리면 된다. <- 이부분 중요!!
import sys
sys.stdin = open('input.txt', 'r')
def solution(people, limit):
ans = 0
people.sort()
while people:
if len(people)==1: # 이부분 추가 잊지 말아야한다.
ans+=1 # 수행하다 1명만 남으면 아래 코드를 수행할 필요없이
break # ans 카운트하고 끝내면 된다
if people[0]+people[-1]<=limit: # 가장 가벼운 사람 가장 무거운 사람 합이 제한 무게 이하면
ans+=1
people.pop()
people.pop(0)
else:
people.pop()
ans+=1
return ans
if __name__ == "__main__":
people = [70, 50, 80, 50]
limit = 100
print(solution(people, limit))
근데 이렇게 하면 딱 한 케이스에서 시간초과가 발생한다.
pop()이 사간을 많이 쓰게 된다고 한다.
딱 2명씩만 뽑는 경우이니 투포인터를 생각해본다.
최종 정답
def solution(people, limit):
left = 0
right = len(people) - 1
ans = 0
people.sort() # 그리디 문제는 무조건 정렬이 절반이다
while left <= right:
ans += 1 # 일단 보트 한대 추가요
if people[left] + people[right] <= limit: # 가장 가벼운 사람과 가장 무거운 사람
left += 1 # 무게초과 안했다면 왼쪽이 한칸 오른쪽으로 이동
right -= 1 # 매 번 오른쪽이 한칸 왼쪽으로 이동 : 무거운 사람 먼저 보내니깐
return ans
if __name__ == "__main__":
people = [70, 50, 80, 50]
limit = 100
print(solution(people, limit))
