시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 1294 | 726 | 633 | 58.939% |
마트료시카는 속이 비어있는 인형이다. 성빈이는 $N$개의 마트료시카를 가지고 있다. $i$번째 마트료시카의 크기는 $a_i$이고, 마트료시카 속은 모두 비어있다.
성빈이는 남아 있는 마트료시카 중에서 $i$번째와 $j$번째$(i \neq j)$ 마트료시카를 고른 뒤에 $i$번째 마트료시카를 $j$번째 마트료시카 속에 넣을 수 있다. 단, $j$번째 마트료시카의 속이 비어있어야 하고, $i$번째 마트료시카보다 $j$번째 마트료시카가 더 커야 한다. 합친 후에는 남아 있는 마트료시카의 개수가 한 개 줄어든다.
성빈이는 마트료시카를 최대한 합쳐서 정리하려고 한다. 성빈이가 마트료시카를 잘 합친다면 남아 있는 마트료시카의 최소 개수는 얼마일까?
첫째 줄에 마트료시카의 개수 $N(1 \le N \le 1\ 000)$이 주어진다.
둘째 줄에 정수 $a_1, a_2, ... , a_N$이 주어진다. $a_i(1 \le a_i \le 10^9)$는 $i$번째 마트료시카의 크기이다.
남아있는 마트료시카의 최소 개수를 출력한다.
3 1 2 3
1
4 2 1 4 2
2
7 3 3 4 5 2 2 3
3
University > 충남대학교 > 2022 충남대학교 SW-IT Contest > Division 1 D번
University > 충남대학교 > 2022 충남대학교 SW-IT Contest > Division 2 F번