별사탕 줍기
실버 V의견: 0
마법의 복도에 \(N\)개의 칸이 일렬로 놓여 있고, \(i\)번째 칸에는 별사탕이 \(a_i\)개 있다 (\(a_i\)가 음수이면 그만큼 사탕을 잃는다).
주인공은 첫 번째 칸에서 출발해 마지막 칸에서 멈춘다. 한 번 이동할 때 바로 이웃한 칸으로는 갈 수 없고, 반드시 한 칸 이상을 건너뛰어 앞으로 이동해야 한다. 방문한 모든 칸의 별사탕을 줍는다.
첫 번째 칸과 마지막 칸은 반드시 방문한다. \(N = 2\)일 때는 두 칸이 이웃해 있어도 둘 다 방문한다.
얻을 수 있는 별사탕의 최대 개수를 구하여라.
- \(1 \le N \le 100\,000\)
- \(-10^9 \le a_i \le 10^9\)
첫째 줄에 칸의 수 \(N\)이 주어진다.
둘째 줄에 각 칸의 별사탕 수 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
얻을 수 있는 별사탕의 최대 개수를 출력한다.
6
3 -1 4 2 -2 6
13
시작(셀 \(1\), \(+3\)) → 셀 \(3\)(+\(4\)) → 셀 \(5\)(−\(2\)) → 도착(셀 \(6\), \(+6\))이면 \(11\)이고, 시작 → 셀 \(3\) → 도착이면 \(3+4+6=13\)으로 이 경로가 최적이다.
3
5 1 5
10
\(N=3\)이면 셀 \(1\)과 셀 \(3\)만 방문 가능(셀 \(2\)는 이웃). 답은 \(5+5=10\).
2
1 2
3
\(N=2\)일 때는 두 셀이 이웃해도 반드시 둘 다 방문한다. 답은 \(1+2=3\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
별사탕 줍기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
별사탕 줍기