구름 점프
실버 I의견: 0
구름 위에서 사는 개구리가 구름 \(1\)번에서 구름 \(N\)번까지 이동하려 한다. 구름 \(i\)에는 에너지 \(e_i\)가 있다 (음수이면 에너지를 잃는다). 방문한 모든 구름의 에너지를 얻는다.
개구리는 현재 구름에서 앞으로 \(1\) 이상 \(K\) 이하의 칸만큼 점프할 수 있다. 단, 크기 \(1\)의 점프를 연속으로 \(M\)번보다 많이 할 수 없다 (크기 \(\ge 2\)인 점프가 끼어들면 연속 횟수는 초기화된다).
구름 \(N\)에 반드시 도달한다고 보장된다. 얻을 수 있는 에너지의 최대 합을 구하여라.
- \(1 \le N \le 3\,000\)
- \(1 \le K \le 10\)
- \(1 \le M \le K\)
- \(-10^6 \le e_i \le 10^6\)
- 구름 \(N\)에 반드시 도달 가능한 입력만 주어진다.
첫째 줄에 구름의 수 \(N\), 최대 점프 크기 \(K\), 허용 연속 소점프 횟수 \(M\)이 공백으로 구분되어 주어진다.
둘째 줄에 구름 \(1\)번부터 \(N\)번까지의 에너지 \(e_1, e_2, \dots, e_N\)이 공백으로 구분되어 주어진다.
얻을 수 있는 에너지의 최대 합을 출력한다.
5 2 1
3 -1 4 2 5
12
\(K=2\)이면 최대 두 칸까지 점프 가능, \(M=1\)이면 크기 \(1\) 점프를 연속 두 번 할 수 없다. 구름 \(1(+3) \to 3(+4) \to 5(+5) = 12\)가 최대.
5 3 2
10 1 1 1 10
22
구름 \(1(+10) \to 5(+10)\) (크기 \(4\)이면 불가, \(K=3\)). \(1\to2\to3\to5\): 소 점프 \(1\to2\to3\)은 연속 두 번이라 가능. 최대 경로는 \(1\to2\to3\to5\)로 \(10+1+1+10=22\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
구름 점프
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구름 점프