[Algorithm] 백준 22354 번 : 돌 가져가기

https://www.acmicpc.net/problem/22354

22354번: 돌 가져가기

 

사실,, 해결 못했다,,,

몇시간을 풀어보고 결국 마지막에 구글링을 했는데,, 다른 사람들도 내가 푼 방식대로 한거 같은데 왜 안되는거야..!!!

일단 내가 푼 코드는 아래와 같다.

N = int(input())
array = list(input())
scores = list(map(int, input().split()))

result = 0

def funcMax(i, j):
    if i > j:
        return i
    else:
        return j

setting = [] 
max_score = scores[0]

# Compression
for i in range(N - 1):
  if (array[i] == array[i + 1]):
    max_score = funcMax(max_score, scores[i + 1])  
    if (i==(N-2)):
      setting.append(max_score)
      break
  else:
    setting.append(max_score)
    max_score = scores[i+1]
    if (i==(N-2)):
      setting.append(max_score)
      break
        
N = len(setting)

# 양옆 삭제
setting.pop(0)
setting.pop(-1)

setting.sort(reverse=True)

# 소수점 올림해주는 꼼수
div_num = (len(setting)+1)/2
div = int(div_num)

for i in range(div):
    result = result + setting[i]

print(result)

 

 

 

풀이 설명

일단 압축먼저 시켜야함. → 두번째 B를 가져간다해도 점수를 못받고 세번째 B를 가져간다고 해도 점수를 못받음 (WBWBWBB 요롷게 됐을 거니까) → 어차피 점수를 받으려면 각 옆자리 돌들의 색이 달라야하니까 압축시켜야함

근데 뭘로 압축? 당연히 점수가 큰 돌로 압축을 시켜야겠지 !!

압축을 시키면 WBWBWB가 되고, 당연히 맨 앞뒤 돌은 뽑아도 점수를 못받으니까 양 끝을 삭제

그럼 BWBW가 되고 결과적으로 뭔 수를 뽑든간데 남은 4개 돌들 4/2 = 2개를 뽑을 수 있음..!!

(양 끝을 삭제시켰을 때, BWBWB와 같이 5개의 돌이 나온다면 5/2 = 2.5 인데, 소수점을 무조건 올림하여 3개의 돌을 뽑기)

당연히 높은 수들로 뽑아야하니 BWBWBW를 내림차순으로 정렬! → 가장 높은 수 2개를 더하면 정답이 출력됨 !