Lv.2arraydp
인접하지 않게 고른 최대 합
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
정수 배열 A가 주어집니다.
인접하지 않은 원소들을 골라 합을 최대로 만드세요. 즉 A[i]를 골랐으면 A[i-1]과 A[i+1]은 고를 수 없습니다.
아무것도 고르지 않아도 되며, 그때 합은 0입니다.
입출력 예
| A | result |
|---|---|
[3, 2, 7, 10] | 13 |
[3, 2, 5, 10, 7] | 15 |
[-1, -2] | 0 |
입출력 예 설명
예 1 — 3과 10을 고르면 13입니다. 2 + 10 = 12보다 큽니다.
예 2 — 3 + 5 + 7 = 15 입니다.
예 3 — 모두 음수라 아무것도 고르지 않는 것이 최선입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(A: int[]) → long
제한 사항
- 답은 64비트 정수 범위입니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(1)
입출력 예
| A | 기대 출력 |
|---|---|
[3,2,7,10] | 13 |
[3,2,5,10,7] | 15 |
[-1,-2] | 0 |
힌트
힌트
"몇 칸을 건너뛸까"가 아니라 **"이 원소를 고를까 말까"**로 생각하세요. 건너뛴 칸 수는 그 선택들의 결과일 뿐입니다.
i를 결정하려면 i-1에 대해 딱 하나만 알면 됩니다. "i-1을 골랐는가." 그래서 상태가 두 개입니다.
skip 쪽에 가 들어가는 것을 빠뜨리기 쉽습니다. A[i]를 안 고를 때 직전은 골랐든 안 골랐든 되기 때문입니다.
초깃값은 , 입니다. 변수 두 개로 줄일 수도 있지만, 서로를 참조하니 갱신 순서에 주의하세요. 헷갈리면 배열을 쓰는 것이 안전합니다.
복잡도 목표
모든 조합을 시도하는 풀이는 당연히 불가능하고, 풀이 역시 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1400 ms | 추정 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1000 ms | 도출됨 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |