| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 92 | 38 | 31 | 39.241% |
길이가 $N$인 수열 $a_1,a_2,\cdots ,a_N$이 주어질 때, 이 수열의 부분 수열 $b_1,b_2,\cdots ,b_M(1\le M\le N)$이 도미노 수열이 되려면 다음과 같은 조건을 만족해야 한다.
\[b_1,b_2,\cdots ,b_M(b_i\le\displaystyle\sum_{j=1}^{i-1}b_j,2\le i\le M)\]
주어진 수열의 부분 수열 중 도미노 수열의 최대 길이를 구해보자.
첫째 줄에 정수 $N(1\le N\le 200,円 000)$이 주어진다.
둘째 줄에 정수 $a_1,a_2,\cdots ,a_N(1\le a_i\le 10^9)$이 공백으로 구분되어 주어진다.
주어진 수열의 부분 수열 중 도미노 수열의 최대 길이를 출력한다.
6 2 3 1 9 4 3
4
부분 수열 중 $\{a_2,a_3,a_5,a_6\} =\{3,1,4,3\}$이 가장 긴 도미노 수열이다.
5 2 1 5 4 3
3
부분 수열 중 $\{a_1,a_2,a_5\} =\{2,1,3\}$이나 $\{a_3,a_4,a_5\} =\{5,4,3\}$이 가장 긴 도미노 수열이다.
7 3 1 7 4 11 12 13
5
부분 수열 중 $\{a_3,a_4,a_5,a_6,a_7\} =\{7,4,11,12,13\}$이 가장 긴 도미노 수열이다.
4 3 1 2 6
4
3 1 2 3
1
부분 수열이란 주어진 수열에서 1ドル$개 이상의 원소를 골라 원래 순서대로 나열한 수열이다.
University > 충남대학교 > 2023 충남대학교 SW-IT Contest > Division 1 M번