풍선 파티
골드 V의견: 0
축제 준비 위원회는 일렬로 \(N\)개의 풍선을 놓았다. 풍선마다 양의 정수 코인 값이 적혀 있다.
코인 수집 게임의 규칙은 다음과 같다.
- 매 턴, 아직 터지지 않은 풍선 중 하나를 골라 터뜨린다.
- 풍선을 터뜨리면, 그 풍선의 값 \(a_i\)와 남아 있는 바로 왼쪽 풍선의 값 \(a_l\), 바로 오른쪽 풍선의 값 \(a_r\)의 곱 \(a_l \times a_i \times a_r\)만큼 코인을 얻는다. 터뜨린 풍선의 왼쪽(혹은 오른쪽)에 남아 있는 풍선이 없으면 그 쪽의 값을 \(1\)로 간주한다.
모든 풍선을 터뜨려서 얻을 수 있는 코인의 최댓값을 구하여라.
- \(1 \le N \le 500\)
- \(1 \le a_i \le 1\,000\)
첫째 줄에 풍선의 수 \(N\)이 주어진다.
둘째 줄에 풍선의 코인 값 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
얻을 수 있는 코인의 최댓값을 출력한다.
4
3 1 5 8
167
풍선을 \(1 \to 5 \to 3 \to 8\) 순서로 터뜨리면 얻는 코인이 \(3 \times 1 \times 5 + 3 \times 5 \times 8 + 1 \times 3 \times 8 + 1 \times 8 \times 1 = 167\)로 최대이다.
2
1 5
10
풍선이 두 개이다. \(5\)를 먼저 터뜨리면 \(1 \times 5 \times 1 = 5\)코인, 그 다음 \(1\)을 터뜨리면 \(1 \times 1 \times 1 = 1\)코인, 합계 \(6\)이다. 반대 순서는 \(1 \times 1 \times 5 + 1 \times 5 \times 1 = 10\)이므로 최대는 \(10\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
풍선 파티
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
풍선 파티