Lv.2arraydp
인접하지 않게 고른 최대 합
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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 — 모두 음수라 아무것도 고르지 않는 것이 최선입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
Function signature
solution(A: int[]) → long
Constraints
- 답은 64비트 정수 범위입니다.
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| A | Expected |
|---|---|
[3,2,7,10] | 13 |
[3,2,5,10,7] | 15 |
[-1,-2] | 0 |
Hint
Hint
"몇 칸을 건너뛸까"가 아니라 **"이 원소를 고를까 말까"**로 생각하세요. 건너뛴 칸 수는 그 선택들의 결과일 뿐입니다.
i를 결정하려면 i-1에 대해 딱 하나만 알면 됩니다. "i-1을 골랐는가." 그래서 상태가 두 개입니다.
skip 쪽에 가 들어가는 것을 빠뜨리기 쉽습니다. A[i]를 안 고를 때 직전은 골랐든 안 골랐든 되기 때문입니다.
초깃값은 , 입니다. 변수 두 개로 줄일 수도 있지만, 서로를 참조하니 갱신 순서에 주의하세요. 헷갈리면 배열을 쓰는 것이 안전합니다.
복잡도 목표
모든 조합을 시도하는 풀이는 당연히 불가능하고, 풀이 역시 효율성 테스트에서 시간 초과가 납니다.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1400 ms | estimated |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |