문제

영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다.

이번 이벤트는 다음과 같다. 순서가 매겨진 여러 장의 카드가 있다. 각각의 카드는 저마다 레벨이 있다.

카드 A에 카드 B를 덧붙일 수 있다. 이때 붙이는 조건은 다음과 같다.

두 카드는 인접한 카드여야 한다.
업그레이드 된 카드 A의 레벨은 변하지 않는다.
카드 합성을 할 때마다 두 카드 레벨의 합만큼 골드를 받는다.

영관이가 골드를 최대한 많이 받을 수 있게 여러분이 도와주자.

예를 들어, c1, c2, c3로 연속된 카드 3개가 있고 각각 레벨이 40,30,30 이라고 하자.

이 카드들을 합치는 과정에서, 먼저 c3에 c2를 합쳐 임시 카드 x1을 만든다. x1의 레벨은 30이고 획득 골드는 60이다. 그 다음엔 c1에 x1을 합쳐 카드 x2를 만들면 레벨이 40이고 70만큼의 골드를 획득할 수 있다. 이때, 영관이가 획득한 골드는 70+60 = 130이다.

다른 방법으로 c1에 c2를 덧붙인 카드 x1을 만들면, x1의 레벨은 40이고 획득한 골드는 70이다.

x1에 c3를 덧붙인 카드 x2의 레벨은 40이고 획득 골드는 70이다. 이때, 영관이가 획득한 골드는 70 + 70 = 140이다. 이외에 더 많은 골드를 받는 방법이 없으므로 140이 획득할 수 있는 최대 골드이다.

입력
카드의 개수 n(1 ≤ n ≤ 1,000)이 주어진다.

다음 줄에 각각 카드의 레벨 Li가 순서대로 주어진다. (0 < Li ≤ 100,000)

출력
영관이가 받을 수 있는 골드의 최댓값을 출력한다.

예제 입력 1

3
40 30 30

예제 출력 1

140

나의 코드

let input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .trim()
  .split("\n");
input.shift();
input = input[0].split(" ").map(Number);

// 문제 풀이
input.sort((a, b) => b - a);
let gold = 0;
for (let i = 1; i < input.length; i++) {
  gold += input[i] + input[0];
}
console.log(gold);

오늘도 그리디~~~
이번 문제도 그리디인만큼 가장 좋은 걸 취하려면 어떻게 해야할지부터 고민해보았다.

카드를 내림차순으로 정렬하고
가장 레벨이 큰 카드에 계속해서 다른 카드를 순차적으로 더해주어야 골드가 가장 크다
오늘 코드스테이츠에서 for문을 빡시게 연습한만큼 오랜만에 for문으로 풀어보았다!

예컨대 내림차순된 배열 [70, 60, 50, 40, 30]이 있다고 하면
70에 60을 더하여 골드 130을 얻고
70에 50을 더하여 골드 120을 얻고
70에 40을 더하여 골드 110을 얻고
70에 30을 더하여 골드 100을 얻을 때 가장 골드의 총합이 크다.

아직까지는 그리디에서 요구하는 패턴만 떠올리면 구현하는 건 어렵지 않다.
좀 더 가면 그렇지 않겠지.. 여튼 다른 그리디 또 풀러갑니다~ 숑숑

---

python으로 다시 풀기

미래에서 왔습니다~~
지금은 2023년 8월 7일.
예전에 자바스크립트로 풀었을 때는 for문을 이용하여 풀었군.
프로젝트 끝나고 python으로 다시 풀어봤는데,
이번에는 반복문을 돌리지 않고
가장 큰 원소, 나머지 원소들의 합산 값, 나머지 원소들의 개수
이렇게 3개를 구한다음 식을 세워 풀었다.
즉

answer = 가장 큰 원소의 레벨 * 나머지 원소의 개수 + 나머지 원소들의 합산 값

이렇게 식을 세워 풀었다.

from sys import stdin as s
from collections import deque

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n = int(s.readline().strip())

cards = [int(i) for i in s.readline().strip().split()]

cards.sort(reverse=True)
q = deque(cards)

max_value = q.popleft()

# 나머지 원소들의 합산 값
sum_of_rest_values = sum(q)

# 나머지 원소들의 개수
count_rest_values = len(q)

answer = sum_of_rest_values + max_value * count_rest_values
print(answer)

시간복잡도는 어차피 sort하는데 가장 많이 소요되므로 두 코드 모두 O(nlogn)으로 볼 수 있겠군.
다만 반복문을 실행하는 데 필요한 시간은 줄였다는 점? 정도는 개선되었다고 할 수 있겠다.
배고프다. 이제 밥먹으러 숑숑~