가장 긴 증가 부분 수열의 개수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
정수 배열 nums가 주어집니다. 몇 개의 원소를 골라 원래 순서대로 읽은 것을 부분 수열이라고 합니다.
값이 순증가(바로 앞 원소보다 반드시 큰)하는 부분 수열 중 가장 긴 것의 길이를 이라고 할 때, 길이가 인 순증가 부분 수열이 몇 개인지 구하세요. 값이 같더라도 고른 위치(인덱스)가 다르면 다른 부분 수열로 셉니다.
답이 매우 커질 수 있으므로 로 나눈 나머지를 반환하세요.
입출력 예
| nums | result |
|---|---|
[1, 3, 5, 4, 7] | 2 |
[2, 2, 2] | 3 |
[1, 2, 1, 2] | 3 |
입출력 예 설명
예 1 — 가장 긴 길이는 4이고 [1, 3, 5, 7], [1, 3, 4, 7] 두 가지입니다.
예 2 — 같은 값은 증가가 아니므로 길이는 1이고, 세 위치 중 하나를 고르는 3가지입니다.
예 3 — 길이 2인 증가 부분 수열은 위치 (0, 1), (0, 3), (2, 3)의 3가지입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(nums: int[]) → int
제한 사항
-
nums.length -
nums[i]
기대 복잡도
- 시간
- O(N log N)
- 공간
- O(N)
입출력 예
| nums | 기대 출력 |
|---|---|
[1,3,5,4,7] | 2 |
[2,2,2] | 3 |
[1,2,1,2] | 3 |
힌트
힌트
각 위치 i에 대해 두 값을 구합니다.
len[i]:nums[i]로 끝나는 가장 긴 증가 부분 수열의 길이cnt[i]: 그런 길이의 부분 수열의 개수
j < i이고 nums[j] < nums[i]인 j들 중 len[j]의 최댓값을 이라 하면 len[i] = M + 1이고,
cnt[i]는 len[j] = M인 j들의 cnt[j]의 합입니다(그런 j가 없으면 len[i] = 1, cnt[i] = 1).
이 "값이 nums[i]보다 작은 것들 중 (최대 길이, 그 개수)"를 빠르게 구하는 것이 핵심입니다.
값을 좌표 압축한 뒤, 펜윅 트리의 각 칸에 (길이, 개수) 쌍을 저장하고 두 쌍을 합칠 때
길이가 큰 쪽을 택하되 길이가 같으면 개수를 더하면 됩니다.
같은 값끼리는 증가가 아니므로 nums[i]보다 엄격히 작은 범위만 질의하세요.
복잡도 목표
모든 j < i 쌍을 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다. 이 필요합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1084 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |