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

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[침몰하는 타이타닉]

 

유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있다. 이 유람선에는 N명의 승객이 타고 있다.

구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보드는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있다. N명의 승객 몸무게가 주어졌을 때, 승객 모두가 탈출하기 위한 구명보트의 최소 개수를 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 자연수 N(5 ≤ N ≤ 1000)와 M(70 ≤ M ≤ 250)이 주어진다.

두 번째 줄에 N개로 구성된 몸무게 수열이 주어진다. (단, 몸무게는 50이상 150 이하)

각 승객의 몸무게는 M을 넘지 않는다. (즉, 탈출을 못하는 경우는 없음)

 

*출력 설명

첫 번째 줄에 구명보트의 최소 개수를 출력하시오.

 

 

---

 

 

풀이(Python)

답안(1)

# 리스트 자료형을 사용한 답안

import sys
sys.stdin = open('AA/input_29.txt', 'rt')

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

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

# 출력 : 3

 

답안(2)

# deque 자료형을 사용한 답안

import sys 
from collections import deque
sys.stdin = open('AA/input_29.txt', 'rt')

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)

# 출력 : 3

 

input_29.txt(입력)

5 140
90 50 70 100 60

 

 

중요내용

1. 해당 문제를 풀어가는 기본적인 원리는 몸무게가 가장 무거운 사람과 몸무게가 가장 가벼운 사람을 한 쌍으로 비교하여 보트에 태울 수 있는지를 확인하는 것이다.
2. while문의 조건으로 리스트 자료형(p)를 넣으면, 해당 리스트의 데이터가 모두 제거되어 빈 리스트가 될 때 반복문이 멈춘다.
3. 만약, 리스트의 데이터가 1개만 남는 경우에는 에러가 발생할 수 있다. (동일한 값을 두번 연산하기 때문)
4. 이러한 에러를 방지하고자 if len(p) == 1:의 코드를 사용하는 것이다. (if절로 리스트의 데이터가 1개만 남은 상황을 제어함)
5. deque 자료형을 사용하면, 리스트 자료형을 사용할 때보다 효율적으로 자료구조를 조작할 수 있다.
6. 즉, deque 자료형을 사용하면 맨 앞의 데이터와 맨 뒤의 데이터를 추출하는 과정에서 데이터의 불필요한 움직임을 최소화 할 수 있다. (리스트 자료형과의 차이점)
7. deque 자료형의 맨 앞 데이터를 추출할 때에는 popleft() 함수를 사용하고, 맨 뒤의 자료형을 추출할 때에는 pop() 함수를 사용하면 된다.
8. 참고로, p = deque(p)는 기존의 리스트 자료형이었던 변수 p를 deque 자료형으로 변환하는 코드이다.