3138 : N개의 숫자 중 K개 선택 최대합

시간 1.000s · 메모리 256MB · 제출 9 · 정답 4

코드제출 문제 풀기

채점기록 통계 묻고답하기

$N$개의 정수로 이루어진 배열에서 $K$개를 골라 합의 최댓값을 구하세요.

단, 선택한 $K$개의 숫자 중 인접한 두 숫자는 고를 수 없습니다. (인덱스가 연속된 원소는 동시에 선택 불가)

[제약 조건]
• $1 \le K \le N \le 20$
• $0 \le (\text{각 정수}) \le 1000$
• 입력되는 모든 값은 정수

첫째 줄에 $N$과 $K$가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.

조건을 만족하며 $K$개를 선택했을 때 최대 합을 출력하세요. 불가능하면 $-1$을 출력하세요.

5 2
3 1 5 2 4

(0번, 2번) 3+5=8, (0번, 4번) 3+4=7, (2번, 4번) 5+4=9... 따라서 최댓값은 9입니다.