BAEKJOON #14241 슬라임 합치기 (Greedy) - python
슬라임 합치기
출처 : 백준 #14241
시간 제한 | 메모리 제한 |
---|---|
2초 | 512 MB |
문제
영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.
모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.
영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다.
둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다.
입출력 예시
예제 입력 1
2
3 4
예제 출력 1
12
예제 입력 2
3
2 2 2
예제 출력 2
12
예제 입력 3
3
1 2 3
예제 출력 3
11
예제 입력 4
3
3 1 2
예제 출력 4
11
풀이
풀이 설명
- 슬라임의 크기를 두 개씩 뽑아서 곱한 값을 점수에 추가하고 더한 값은 다시 배열에 집어 넣어 똑같은 과정을 반복한다.
python code
# 백준 14241번
from sys import stdin
from collections import deque
def slime(n, slimes):
slimes.sort(reverse=True) # 큰 순서대로 정렬하기
deq = deque()
for i in range(n):
deq.append(slimes[i])
result = 0 # 얻는 점수
while (len(deq) > 1):
x = deq.popleft()
y = deq.popleft()
result += x*y # 곱한 만큼 점수로 추가
deq.appendleft(x+y) # 합친 슬라임은 다시 deq에 집어넣기
return result # 점수 반환
n = int(stdin.readline())
slimes = list(map(int, stdin.readline().split()))
result = slime(n, slimes)
print(result)
Author And Source
이 문제에 관하여(BAEKJOON #14241 슬라임 합치기 (Greedy) - python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nathan29849/BAEKJOON-14241저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)