[Python] 28464번 Potato

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

---

 

24/04/16

 

 

아주 간단한 그리디 문제다.

---

 

문제 접근 방식:

 

 

편의 상 박 모씨를 A, 성우를 B라고 부르겠다.

 

문제에서 요구하는 것은 A가 감자튀김을 최대한 많이, B가 감자튀김을 최대한 적게 가져가도록 하는 것이다.

 

A가 먼저 감자튀김을 가져간다고 했다.

 

상식적으로 생각해보면, A가 감자튀김을 최대한 많이 가져가기 위해서는 감자튀김의 양이 가장 많은 접시부터 순서대로 가져가는 것이 이득일 것이다.

 

마찬가지로 B가 감자튀김을 최대한 적게 가져가도록 하기 위해서는 감자튀김의 양이 가장 적은 접시부터 순서대로 가져가는 것이 이득일 것이다.

 

따라서, 주어진 배열을 오름차순으로 정렬하여, 배열의 절반은 A가, 배열의 절반은 B가 가져가도록 하면 된다.

 

이때, A가 먼저 가져간다고 했으므로, 접시가 홀수 개일때는 A가 하나 더 많이 가져감에 유의하여 구현하면 된다.

---

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

# 28464번 Potato
# 그리디, 정렬
import sys
input = sys.stdin.readline

N = int(input())
A = sorted(map(int, input().split()))
sung_woo, park = 0, 0
for i in range(N):
    if i >= N//2:
        park += A[i]
    else:
        sung_woo += A[i]
print(sung_woo, park)