[Algorithm] BAEKJOON 14241번: 슬라임 합치기 (Python)

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

 

 

 

문제

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

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

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

 

입력

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

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

 

출력

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

 

 

 

 

 

풀이

양쪽 끝에서 데이터의 삽입과 삭제 연산을 간편하게 할 수 있는 파이썬의 덱 자료구조를 사용해서 앞에서 두 개의 슬라임을 제거하여 합친 후 그 결과를 앞에 다시 넣는 과정을 반복하여 풀어주었다.

 

 

Python 소스 코드

from collections import deque

N = int(input())

# 슬라임의 크기를 리스트로 받아 덱(deque)으로 변환
slime_sizes = deque(list(map(int, input().split())))

# 최종 점수를 저장할 변수 초기화
max_score = 0

# 슬라임이 하나 남을 때까지 반복
for _ in range(N - 1):
    # 가장 앞의 두 슬라임 크기 추출
    x = slime_sizes.popleft()
    y = slime_sizes.popleft()

    # 두 슬라임을 합쳐서 얻는 점수 계산
    max_score += x * y

    # 합친 슬라임의 크기를 덱의 앞에 추가
    slime_sizes.appendleft(x + y)

print(max_score)