[Python] 8094번 Canoes

https://www.acmicpc.net/problem/8094

---

 

24/11/29

 

 

간단한 정렬 + 두 포인터 + 그리디 문제다.

---

 

문제 접근 방식:

 

 

간단하게 문제를 요약하면 다음과 같다.

 

카누 한 대에는 최대 사람을 두 명 태울 수 있다. 문제에서 카누 한 대의 최대 중량 제한 $W$를 주고, $N$명의 사람들의 몸무게를 준다. 모든 사람을 카누에 태우려고 할 때, 필요한 카누의 최소 대수를 구하는 것이다.

 

가장 무거운 사람과 가장 가벼운 사람을 짝지어서 태우는 방법을 먼저 생각했다.

 

예를 들어 무게 제한이 $100$이라면, $90$과 $10$을 짝지어서 태울 수 있을 것이다.

 

만약 그게 불가능 하다면, $90$만 먼저 태우고, $10$은 그 다음으로 무거운 사람과 짝지어서 태우면 될 것이다.

 

그래서 그냥 그리디적으로 생각하면 되고, 가장 무거운 사람과 가장 가벼운 사람을 표현하기 위해서는 정렬과 투포인터를 사용하면 된다.

 

이때, 카누 한 대가 더 필요할 지 더 필요하지 않을지에 대한 경우가 갈릴 수도 있다.

 

가벼운 사람을 나타내는 포인터 $s$가 무거운 사람을 나타내는 포인터 $e$보다 작을 동안만 카누를 태우는 과정을 실행하도록 했는데, 만약 $s == e$인 경우라면, 한 사람이 남는 경우이므로 카누 한 대가 더 필요하다는 뜻이 된다.

 

따라서 이를 통해 구현하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 8094번 Canoes
# 그리디, 정렬, 두포인터
import sys
input = sys.stdin.readline

W = int(input()) # 무게 제한
N = int(input()) # 인원 수
P = sorted(int(input()) for _ in range(N))
s, e = 0, N-1
ans = 0
while s < e:
    if P[s]+P[e] <= W:
        s += 1
        e -= 1
        ans += 1
    else:
        e -= 1
        ans += 1
if s == e:
    ans += 1
print(ans)