[그리디 알고리즘] ▲ 12845번 - 모두의 마블

[백준] 12845번 - 모두의 마블

풀이 시간: 30~35분 이내

 

(풀이1) 문제 그대로 구현한 방법

1) 문제 해결 아이디어

아이디어를 떠올리는 것은 어렵지 않았으나 계속 런타임 에러(TypeError)가 났다. 

주어진 테스트 케이스에서는 값이 잘 나왔으나 다른 테스트 케이스의 경우 제대로 된 값이 오류가 발생했다.

 

<카드 A에 카드 B를 덧붙일 수 있는 조건>

1. 두 카드는 인접한 카드

2. 합성한 카드 A의 레벨은 변하지 않음

 

카드를 합성할 때마다 카드A, B 레벨의 합만큼 골드를 받음

<골드를 최대로 받기 위한 방법>

1. 레벨의 최댓값(max)를 기준으로 계속 오른쪽으로 합성하기(최댓값의 인덱스가 맨 마지막이 될 때까지)

2. 최댓값(max)기준으로 계속 왼쪽으로 합성하기(남은 카드가 1개가 될 때까지)

 

첫번째 오류. 리스트 값 삭제 후 리스트 길이에 대한 처리

리스트 값을 삭제하고 리스트 길이를 업데이트 해주지 않아 인덱스 범위를 벗어나 오류가 났다.

 

2) 소스코드

n = int(input())    # 카드 개수
l = list(map(int, input().split()))  # 카드 레벨
gold = 0  # 골드 수
max = max(l)  # 최고 레벨
max_idx = l.index(max)  # 최고 레벨 인덱스

while True:
  n = len(l)  # 남은 카드 수
  target = 0  # 합성할 카드
  
  # 카드가 1장밖에 안남았으면 탈출
  if(n == 1):
    break

  # 맨 끝 인덱스가 아니면 오른쪽 합성
  if(0 <= max_idx < n - 1):
    target = l[max_idx + 1]
    gold += (max + target)
    del l[max_idx + 1]  # 합성 카드 삭제
  # 맨 끝 인덱스이면 왼쪽 합성
  elif(max_idx == n - 1):
    target = l[max_idx - 1]
    gold += (max + target)
    del l[max_idx - 1]  # 합성 카드 삭제
    max_idx -= 1  # 최댓값 인덱스 수정
      
print(gold)

 

 

(풀이2) 문제의 본질을 이해한 방법

1) 문제 해결 아이디어

인접한 두 카드에 한해서만 합성을 진행할 수 있다는 점에서 위에서는 인접한 카드에 대하여 하나하나 계산을 했지만 사실은 굳이 그럴 필요가 없는 문제다. 왜냐면 결국엔 합성한 카드A의 레벨은 변하지 않기 떄문이다. 최댓값을 기준으로 합성을 계속 진행하기 때문에 인접한 카드들을 다 합성하면 사실 더하는 순서와 상관없이 결과는 같다.

 

<골드를 최대로 받기 위한 방법>

1. 레벨(l)을 내림차순한다. (여기서 내림차순을 하는 이유는 단순히 최댓값을 쉽게 구하고 최댓값 외의 숫자들의 합을 편하게 구하기 위함이다.)

2. 최댓값(max)를 제외한 나머지 숫자의 개수(n - 1) 만큼 최댓값을 더하고 나머지 값들의 합을 구한다.

합성을 1번 할 때 받는 gold 개수 = 최댓값 + 합성할 값 => (n - 1) 번 반복

 

2) 소스코드

n = int(input())    # 카드 개수
l = list(map(int, input().split()))  # 카드 레벨
l.sort(reverse = True)  # 내림차순 정렬
max = l[0]  # 최댓값

gold = max * (n - 1) + sum(l[1:])
print(gold)

 

[참고] https://sjy1218vv.tistory.com/197

[알고리즘]BOJ_12845_모두의 마블(파이썬 내림차순 정렬)