[Python 알고리즘] 백준 128475번 : 모두의 마블

문제

• 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다.카드 A에 카드 B를 덧붙일 수 있다. 이때 붙이는 조건은 다음과 같다.
  1. 두 카드는 인접한 카드여야 한다.
  2. 업그레이드 된 카드 A의 레벨은 변하지 않는다.
  카드 합성을 할 때마다 두 카드 레벨의 합만큼 골드를 받는다.예를 들어, c1, c2, c3로 연속된 카드 3개가 있고 각각 레벨이 40,30,30 이라고 하자.다른 방법으로 c1에 c2를 덧붙인 카드 x1을 만들면, x1의 레벨은 40이고 획득한 골드는 70이다.
• x1에 c3를 덧붙인 카드 x2의 레벨은 40이고 획득 골드는 70이다. 이때, 영관이가 획득한 골드는 70 + 70 = 140이다. 이외에 더 많은 골드를 받는 방법이 없으므로 140이 획득할 수 있는 최대 골드이다.
• 이 카드들을 합치는 과정에서, 먼저 c3에 c2를 합쳐 임시 카드 x1을 만든다. x1의 레벨은 30이고 획득 골드는 60이다. 그 다음엔 c1에 x1을 합쳐 카드 x2를 만들면 레벨이 40이고 70만큼의 골드를 획득할 수 있다. 이때, 영관이가 획득한 골드는 70+60 = 130이다.
• 영관이가 골드를 최대한 많이 받을 수 있게 여러분이 도와주자.
• 이번 이벤트는 다음과 같다. 순서가 매겨진 여러 장의 카드가 있다. 각각의 카드는 저마다 레벨이 있다.

입력

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

# Case 1
3
40 30 30

출력

# Case 1
140

내가 제출한 풀이 - 정답

1차 (72ms)

import sys

n = int(sys.stdin.readline().strip())
l = list(map(int, sys.stdin.readline().strip().split()))

i = l.index(max(l))
l_len = len(l) - 1
left, right = i, i
res = l[i]
max_num = 0


def up_right():
    global right, res, max_num

    right += 1
    res += max_num + l[right]
    max_num = max(max_num, l[right], l[right - 1])


def up_left():
    global left, res, max_num

    left -= 1
    res += max_num + l[left]
    max_num = max(max_num, l[left], l[left + 1])


def up_vs():
    if l[left - 1] > l[right + 1]:
        up_left()
    else:
        up_right()


while True:
    if left == 0 and right == l_len:
        break
    elif left <= 0:
        up_right()
    elif right >= l_len:
        up_left()
    else:
        up_vs()

print(res)

음,, 간단한 문제를 좀 어렵게 풀있다.

가장 큰 수를 기준으로 왼쪽 오른쪽을 지정하는 좌표를 둬 서로 비교해가며, 큰 쪽으로 더하는 방식을 하였다. 사실 오름차순 정렬하면 되는 것인데 정렬하지 않고 푼 것이다. (왜  굳이 어렵게 푼거지?..)

 

2차 (68ms)

import sys

n = int(sys.stdin.readline().strip())
l = list(map(int, sys.stdin.readline().strip().split()))

l.sort(reverse=True)

res = 0

for i in range(1, len(l)):
    res += l[0] + l[i]

print(res)

매우 간단하게 풀어냈다.

왜 처음에는 오름차순으로 잘 정렬 해놓고선 갑자기 배열에 좌표를 찍어나가며 풀었던 것인가..

문제풀이

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

이러한 부분을 보면 항상 합칠 때마다 합치는 기준 카드의 레벨이 계속 더해지는 것을 알 수가 있다.

40, 30, 20, 30을 예로 들어보자.

1. 40 + 30 = 70
2. 70 + 30 + 40 = 140
3. 140 + 20 + 40 = 200
4. 200 + 30 + 40 = 270

2~4번째 과정에서 합치는 카드에 레벨인 40을 계속 더했다.

 

근데 여기서 한 가지 트릭을 발견할 수 있다.

가장 큰 수를 먼저 잡고 다 더하면 되는 것이다. 합성카드의 레벨은 지속적으로 들어오는 것이므로 골드를 많이 받게 해준다.

 

오름차순으로 정렬하고 다시 봐보자.

40, 30, 30, 20

1. 40 + 30 = 70
2. 70 + 30 + 40 = 140
3. 140 + 30 + 40 = 210
4. 210 + 20 + 40 = 270

그렇다. 가장 큰 수를 얻은 후 나머지는 순서와 상관없이 더하면 최대 골드를 흭득할 수 있다.