3201 : N개의 숫자 중 K개 선택 최대합 2
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 8
•통과: 2
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 배열에서 $K$개를 골라 합의 최댓값을 구하세요.
단, 선택한 $K$개의 숫자 중 인접한 두 숫자는 고를 수 없습니다. (인덱스가 연속된 원소는 동시에 선택 불가)
[제약 조건]
• $1 \le K \le N \le 2\,000$
• $0 \le (\text{각 정수}) \le 100\,000$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N$과 $K$가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
조건을 만족하며 $K$개를 선택했을 때 최대 합을 출력하세요. 불가능하면 $-1$을 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 2
3 1 5 2 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
9
도움
[파이썬 재귀(DFS) 작성 시 주의사항]
• 파이썬의 기본 최대 재귀 깊이(Call Stack Limit)는 1,000회로 제한되어 있습니다.
• 이 문제에서는 원소를 선택하지 않고 다음 칸으로 탐색(
• 따라서 파이썬으로 탑다운(재귀 + 메모이제이션) 방식을 구현할 경우, 코드 상단에 반드시 재귀 제한을 늘려주는 코드를 포함해야
• 파이썬의 기본 최대 재귀 깊이(Call Stack Limit)는 1,000회로 제한되어 있습니다.
• 이 문제에서는 원소를 선택하지 않고 다음 칸으로 탐색(
dfs(idx + 1, cnt))할 때 최대 $N = 2,000$층까지 함수 호출이 중첩됩니다.• 따라서 파이썬으로 탑다운(재귀 + 메모이제이션) 방식을 구현할 경우, 코드 상단에 반드시 재귀 제한을 늘려주는 코드를 포함해야
Recursionerror (런타임 에러)를 방지할 수 있습니다.import sys
sys.setrecursionlimit(100000)
for 반복문을 활용하는 상향식(Bottom-up) DP로 구현할 경우 함수 호출 스택을 사용하지 않으므로 재귀 깊이 제한의 영향을 받지 않습니다.)