본문 바로가기

알고리즘

마라탕 많이 먹기

Best 20 · 12번Lv. 2동적 계획법

마라탕 많이 먹기

소울곰이 흠모하는 마라탕

문제 설명

NPC 소울곰은 영혼을 가지면서 인간이 먹는 음식을 먹을 수 있게 되었습니다. 소울곰은 평소에 흠모하던 마라탕 가게에 방문하려 합니다. 소울곰은 얼마나 먹어야 하는지 모르고, 광산에서 자주 나올 수도 없기 때문에 최대한 많은 양의 재료를 먹고 싶습니다. 하지만 마라탕 가게의 재료는 가져갈 수 있는 최대 개수가 정해져있습니다.

마라탕의 재료는 아래와 같으며, 재료당 넣을 수 있는 재료의 최대 개수 배열이 주어집니다.

[두부, 버섯, 당면, 숙주, 청경채, 배추, 감자, 고기]

인접한 재료끼리는 상성이 좋지 않아 함께 넣을 수 없습니다. 소울곰이 최대한 많이 담을 수 있는 재료의 양을 반환하세요.


제한 사항

  • 재료 배열은 항상 8개로 고정입니다.
  • 재료당 넣을 수 있는 최대 개수는 배열 안에 숫자로 표시됩니다. [1, 2, 3, 4, 10, 20, 30, 40]이라면 두부는 1개, 버섯은 2개, 당면은 3개, 숙주는 4개, 청경채는 10개, 배추는 20개, 감자는 30개, 고기는 40개입니다.
  • 각 재료의 최대 개수는 1개 이상 1,000,000개 이하의 정수입니다.
  • 재료를 넣을 때는 그 재료의 최대 개수만큼 모두 넣습니다. 재료는 한 줄로 놓여 있어 두부와 고기(처음과 끝)는 이웃하지 않습니다.

입출력 예

입력출력
[2, 4, 1, 3, 5, 8, 8, 6]21
[10, 2, 5, 2, 7, 9, 3, 5]29
[12, 9, 7, 8, 6, 2, 2, 6]31

입출력 설명

마라탕 재료의 개수가 담긴 배열 [2, 4, 1, 3, 5, 8, 8, 6]을 입력받습니다.

재료 두부 2개를 담았다고 했을 때 인접한 4는 재료로 넣을 수 없습니다. 한 칸을 건너뛰고 1을 더합니다. 여기서 1을 더하는 것이 좋을지, 그다음 숫자인 3을 더하는 것이 좋을지, 5를 더하는 것이 좋을지는 더해진 수의 최댓값으로 비교해야 합니다.

2로 시작했을 때 최대로 담을 수 있는 양은 19(2+3+8+6)입니다. 그런데 처음에 4로 시작하면 21(4+3+8+6)을 얻을 수 있습니다. 따라서 답은 21이 됩니다.

예시 테스트

#입력기대값
1[2, 4, 1, 3, 5, 8, 8, 6]21
2[10, 2, 5, 2, 7, 9, 3, 5]29
3[12, 9, 7, 8, 6, 2, 2, 6]31

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.