백준 12845. 모두의 마블 - 문제풀이 (Python/파이썬) (그리디 알고리즘)

🔎 12845번. 문제 보기
https://www.acmicpc.net/problem/12845

💡 문제 풀기 전
나는 개인적으로 문제가 긴 걸 좋아한다. 왜냐면 문제가 길수록 문제 풀이 방향성을 많이 알려주는 듯한 느낌이 들어서..ㅎㅎ 근데 이번 문제는 갑자기 이 카드 저 카드 들이닥치고 레벨에 골드까지 나와서 모두의 마블이 낯선 나에게 혼란을 주었다. 그래도 천천히 읽으면서 문제를 이해하고 코드를 작성하니 생각보다 쉽게 풀렸다.

문제를 이해하고 난 후의 생각은 '그냥 입력받은거 오름차순해서 계속 첫번째꺼랑 비교해주면 되겠네' 정도!

문제 이해하느라 끄적거린 나의 흔적 ㅎㅎ..

📋 코드 보기

from sys import stdin

bin = stdin.readline()
c = list(map(int, stdin.readline().split()))
c.sort(reverse=True)
result = 0

for i in range(len(c)):
    if i <= 1:
        result += c[i]
    else:
        result += c[0]+c[i]

print(result)

🥕 코드 풀이 및 관련 개념

문제 풀이 아이디어

이해하는데 시간이 좀 필요했다.

• 레벨 : 두 카드를 합성할 때 값이 큰 걸로 유지됨
• 골드 : 기존 골드값(초기값 0) + 합성한 두 카드의 레벨을 합한 값

bin = stdin.readline()
c = list(map(int, stdin.readline().split())) # 각각의 카드 레벨 입력
c.sort(reverse=True) # 내림차순 정렬
result = 0  # 골드값

사실 처음에 받는 수는 필요 없어서 대충 입력만 해뒀다.
c 리스트에 카드의 레벨을 각각 받아주는데
처음에 레벨이 가장 높은 카드와 합성해야 해야 처음부터 끝까지 가장 높은 레벨을 유지할 수 있다. 그래서 내림차순으로 변경해주었다.

for i in range(len(c)): 
    if i <= 1:          # 첫 합성
        result += c[i]  
    else:               # 이미 합성한 카드 + 기존 카드
        result += c[0]+c[i]

문제의 의도를 잘 파악했다면 위 코드도 쉽게 이해할 수 있다 :)