
문제 설명
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개도 함께 채점해요.