미술관 전시 경로
골드 III의견: 0
미술관 큐레이터 지아는 \(N\)점의 작품을 입고된 순서대로 번호를 붙였다. 각 작품에는 정수 가중치(예술 점수)가 있다.
지아는 작품을 감상하는 경로를 정하려 한다. 경로는 번호 순서를 유지하면서 예술 점수가 엄격히 증가하는 작품들의 부분 수열이다. 가장 긴 경로의 길이와, 그 길이를 달성하는 서로 다른 경로의 수를 \(1\,000\,000\,007\)로 나눈 나머지를 구하여라.
경로는 같은 위치의 작품 집합이면 같은 경로로 본다.
- \(1 \le N \le 100\,000\)
- 각 작품의 예술 점수는 \(1\) 이상 \(10^9\) 이하의 정수이다.
첫째 줄에 작품 수 \(N\)이 주어진다.
둘째 줄에 입고 순서대로 각 작품의 예술 점수 \(N\)개가 공백으로 구분되어 주어진다.
최장 증가 부분 수열의 길이와 그 길이를 달성하는 경로의 수를 \(1\,000\,000\,007\)로 나눈 나머지를 공백으로 구분해 한 줄에 출력한다.
5
1 3 2 3 4
4 1
수열 \(1, 3, 2, 3, 4\)에서 최장 증가 부분 수열의 길이는 \(4\)이다. 유일한 LIS는 값 \(1 \to 2 \to 3 \to 4\) (인덱스 \(0, 2, 3, 4\))이므로 경로 수는 \(1\)이다.
3
1 2 3
3 1
\([1, 2, 3]\) 하나뿐이므로 길이 \(3\), 가짓수 \(1\)이다.
riseoj 작성
출처 Original
평가 및 의견
미술관 전시 경로
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
미술관 전시 경로