7314 : 1학년 마무리 종합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정렬, 이분탐색, 재귀의 세 가지 기법을 모두 활용하는 종합 문제입니다.
$N$개의 정수 배열이 주어질 때 다음 세 가지를 계산하여 출력하십시오.
1. LIS: 이분탐색을 활용한 최장 증가 부분수열의 길이 ($O(N \log N)$)
2. Sum: 정렬 후 전체 합
3. Max: 정렬된 배열에서 이분탐색으로 찾은 최댓값
[제약 조건]
• 입력되는 모든 수는 정수입니다.
$N$개의 정수 배열이 주어질 때 다음 세 가지를 계산하여 출력하십시오.
1. LIS: 이분탐색을 활용한 최장 증가 부분수열의 길이 ($O(N \log N)$)
2. Sum: 정렬 후 전체 합
3. Max: 정렬된 배열에서 이분탐색으로 찾은 최댓값
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
LIS: [LIS 길이]Sum: [전체 합]Max: [최댓값]
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8
5 1 4 2 8 3 7 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
LIS: 4
Sum: 36
Max: 8도움
LIS는
bisect_left를 이용한 tails 배열로 구합니다. Sum은 sorted(arr) 후 sum(), Max는 정렬 후 마지막 원소 또는 max()로 구합니다.