Funcia
Lv.3binary-searchdpfenwick-tree

가장 긴 증가 부분 수열의 개수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 nums가 주어집니다. 몇 개의 원소를 골라 원래 순서대로 읽은 것을 부분 수열이라고 합니다.

값이 순증가(바로 앞 원소보다 반드시 큰)하는 부분 수열 중 가장 긴 것의 길이를 LL이라고 할 때, 길이가 LL인 순증가 부분 수열이 몇 개인지 구하세요. 값이 같더라도 고른 위치(인덱스)가 다르면 다른 부분 수열로 셉니다.

답이 매우 커질 수 있으므로 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지를 반환하세요.

입출력 예

numsresult
[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

제한 사항

  • 1≤N=1 \le N = nums.length ≤100,000\le 100{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9

기대 복잡도

시간
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]의 최댓값을 MM이라 하면 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 쌍을 확인하는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다. O(Nlog⁡N)O(N \log N)이 필요합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251084 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.