[이분탐색(결정알고리즘)][그리디 알고리즘] - 침몰하는 타이타닉(그리디 알고리즘)

오답

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

weight.sort()
cnt = 0
s= 0 

for i in range(n):
    print(weight[i])
    if s + weight[i] <= m:
        s += weight[i]
        print("+ s = ", s)
    else:
        cnt += 1
        s = weight[i]
        print("s = ",s)
print(cnt)

• 근접한 작은 수끼리 더해가는 방식을 사용했는데 이 문제의 경우 사람의 수가 2명으로 제한되어 있었다.
• 그렇다면 2명끼리 묶어서 사용하는 방법은 최댓값과 최솟값을 사용해 더해보고 큰지 작은지를 확인한 다음 작으면 그 값을 빼내는 것이 일반적이다

문제 풀이

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

weight.sort()
cnt = 0

while weight:
    if len(weight) == 1:
        cnt += 1
        break
    if weight[0] + weight[-1] > m:
        weight.pop()
        cnt += 1
    else:
        weight.pop(0)
        weight.pop()
        cnt += 1
print(cnt)

• 요소가 1개 남았을 땐 보트에 혼자 태우고 반복문을 종료시킨다.