침몰하는 타이타닉(그리디)
유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 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
풀이
정렬해준 다음,
가장 무거운 사람과 가장 가벼운 사람을 비교하여
m보다 크면, 가장 무거운 사람만 탈 수 있고
m보다 작으면, 두 사람은 탈 수 있다.
따라서 0번째와 n-1 번째 인덱스를 비교하면서 구명보트에 태우고,
그 다음은 1번째와 n-2 번째, 이렇게 비교하면서 태우면 된다.
코드1
n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
lt, rt = 0, n-1
cnt = 0
while lt<=rt:
if arr[lt]+arr[rt] > m:
lt+=1
cnt+=1
else: #arr[lt]+arr[rt] <= m
lt+=1
rt-=1
cnt+=1
print(cnt)코드2
lt와 rt의 인덱스를 지정해서 풀지 않고,
큐를 이용해서 풀 수 있다.
가장 무거운 사람은 혼자 타고 나가고
무게가 맞는 무거운 사람과 가벼운 사람이 타고 나가는 방식을 이용한다.
그리고 마지막에 한명만 남았을 때는 혼자 타고 나간다.
n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
cnt = 0
while arr:
if len(arr)==1: # 한명만 남았을 때
cnt+=1
break
if arr[0]+arr[-1]>m:
arr.pop() # 가장 무거운 사람 구명보트 타고 탈출
cnt += 1
else:
arr.pop(0)
arr.pop()
cnt += 1
print(cnt)리스트를 이용하여 pop을 하면,
pop()으로 하나씩 뺄 때마다 맨 뒤 인덱스가 줄어들거나
pop(0)으로 뺄 때마다 인덱스가 줄어든다.
따라서 땡기는 연산을 계속 하게 되므로 비효율적으로 계산하게 된다.
코드3 : deque 이용
from collections import deque
n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
arr = deque(arr) ### arr의 자료구조는 deque가 된다.
cnt = 0
while arr:
if len(arr)==1: # 한명만 남았을 때
cnt+=1
break
if arr[0]+arr[-1]>m:
arr.pop() # 가장 무거운 사람 구명보트 타고 탈출
cnt += 1
else:
arr.popleft() ### pop(0) 대신 popleft()
arr.pop()
cnt += 1
print(cnt)