[백준] 그리디 알고리즘 - 슬라임 합치기 (14241번) #파이썬#python

슬라임 합치기 (14241번)

시간 제한 : 2초 메모리 제한 : 512 MB

 

---

 

문제

 

영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.

모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.

영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

---

입력

 

첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다.

둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다.

---

출력

 

첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다.

---

예제 입력

 

2
3 4

---

예제 출력

 

12

---

해답

 

N = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)

sum = 0
score = 0
total = 0

for i in range(0, N-1):
    score = a[i] * a[i+1]
    a[i+1] = a[i] + a[i+1]
    total = total + score

print(total)

---

풀이

 

입력 N과 리스트 a를 입력받습니다. 그리고 sort() 함수와 reverse 속성을 이용하여 리스트 a를 내림차순으로 정렬해줍니다.
그리고 계산에 필요한 sum, score, total 변수를 초기화해줍니다.
for 반복문 안에서 i가 0일 때, a[1]에 a[0] + a[1]을 넣어주는 방식으로 구현하였습니다.
score에 a[i]와 a[i+1]을 곱한 값을 저장하고, 이를 total 변수에 누적시켜 주었습니다.
"리스트를 내림차순으로 정렬하여 주어진 계산을 수행한다"라는 접근만 하면 구현은 쉬운 문제였습니다.