.PNG)
29. 침몰하는 타이타닉(그리디)
유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 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명 사람들 #보트 한개당 감당 무게 #구명보트는 두명 이하
n, m =map(int, input().split())
w=list(map(int, input().split()))
w.sort()
cnt=0
for i in range(n) :
k=m-w[i]
for j in range(n-1,i,-1):
if k>=w[j]:
cnt+=1
break
print(n-cnt)
print(cnt)입력값3부터 사소하게 어긋하기 시작한다. 어떤 부분이 잘못된건지 파악 불가능
===>살펴보니 중복되는 부분이 존재할 수 밖에 없다ㅠㅠ
<풀이>
n, m =map(int, input().split())
w=list(map(int, input().split()))
w.sort()
cnt=0
while w:
if len(w)==1:
cnt+=1
break
if w[0]+w[-1]>m:
w.pop()
cnt+=1
else :
w.pop(0)
w.pop()
cnt+=1
wrint(c)<풀이> : deque를 이용
- 리스트에서 가장 앞의 원소를 제거할 때 pop(0)으로 풀 수도 있지만 그렇게 하면 리스트에서 pop하고 남은 원소들을 정렬하는 과정이 매번 추가되기 때문에 비효율적이다.
from collections import deque
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)<다른 분들 풀이> (1)
n,m=map(int,input().split())
w=list(map(int,input().split()))
w.sort()
cnt=0
lt=0
rt=n-1
while lt<=rt:
if w[lt]+w[rt]<=m:
cnt+=1
lt+=1
rt-=1
else:
rt-=1
cnt+=1
print(cnt)<다른 분들 풀이> (2)
cnt=0
s=0
e=n-1
while s<=e:
if a[s]+a[e]<=m:
s+=1
cnt+=1
e-=1
print(cnt)<반성점>
- 너무 생각이 부족한 것 같다
<배운 점>
- 무게순으로 정렬을 하고 계속 선택해 나갔다면 그리디에 속한다고 볼 수 있다
- 다른 분들처럼 사고하는 습관을 들이자
- deque: que이지만 양쪽에서 삽입/삭제가 가능한 자료구조이다. pop()연산은 list와 크게 차이가 없지만 deque가 빛을 발하는 것은 앞쪽에 삽입/삭제 연산을 할 때이다. list에서 insert/pop(0) 정렬하는 과정이 추가되어 O(n) 시간이 걸리지만, deque는 appendleft()/popleft()를 사용하면 O(1)의 시간으로 더 빠르게 처리할 수 있다. 다만 deque는 연결리스트로, 생성되는데 시간이 걸리므로 스택에서는 list, 큐에서는 deque를 사용하는 것이 효율적이다.
