문제 태그

• 그리디
• 정렬

아이디어

1. 어차피 “검흰흰흰검흰” 일 경우 흰색x3인 구간에서 모두 가져갈 수 없음 → 흰색x3인 구간에서 하나만 가져갈 수 있기 때문에 그 중 가장 큰 것만 냅둠
2. 1번의 과정을 거치면 결국 흰검흰검흰검 … or 검흰검흰검흰으로 나옴
3. 양 사이드는 못가져감으로 양 끝사이드는 슬라이스
4. 우리는 결국 가장 큰 돌부터 가져가는데 이때 가져갈 수 있는 돌의 최대 개수는 ceil(길이/2)임 이유는 하나의 돌을 가져가면 옆에 있는 돌을 포기해야함.
   1. 만약 최적해의 돌이 퍼져있다면 옆에 있는 돌 중에 최적해가 아닌것이 있음은 자명함
   2. 만약 한곳에 뭉쳐있다면 어느 한곳은 무조건 양쪽이 최적해가 아닌것이 존재함이 자명함

정답

import math

N = int(input())
color = input()
weight = list(map(int, input().split()))

now_color = color[0]
max_weight = weight[0]

stones = list()
for i in range(1,N):
    if color[i] != now_color:
        stones.append(max_weight)
        max_weight = weight[i]
        now_color = color[i]
    else:
        max_weight = max(max_weight,weight[i])
stones.append(max_weight)

sorted_arr = sorted(stones[1:len(stones)-1],reverse=True)
answer = 0
for i in range(math.ceil(len(sorted_arr)/2)):
    answer += sorted_arr[i]
print(answer)