8021 : 타워
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 6
•통과: 1
•만든사람: suakii
문제 설명
$N$개의 블록이 주어집니다. 이 블록들을 사용하여 타워를 쌓으려고 합니다.
블록들을 주어진 순서대로 하나씩 처리하며 타워를 쌓아야 하며, 어떤 블록 위에 다른 블록을 올리려면 위에 놓는 블록의 크기가 아래에 있는 블록의 크기보다 반드시 엄격하게 더 작아야 합니다.
기존 타워 위에 올릴 수 없는 경우 새로운 타워를 시작해야 합니다.
블록들을 주어진 순서대로 쌓을 때, 필요한 최소 타워의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le k_i \le 10^9$ (각 블록의 크기)
블록들을 주어진 순서대로 하나씩 처리하며 타워를 쌓아야 하며, 어떤 블록 위에 다른 블록을 올리려면 위에 놓는 블록의 크기가 아래에 있는 블록의 크기보다 반드시 엄격하게 더 작아야 합니다.
기존 타워 위에 올릴 수 없는 경우 새로운 타워를 시작해야 합니다.
블록들을 주어진 순서대로 쌓을 때, 필요한 최소 타워의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le k_i \le 10^9$ (각 블록의 크기)
입력 설명
첫째 줄에 블록의 개수 $N$이 주어집니다.
둘째 줄에 $N$개의 정수 $k_1, k_2, \ldots, k_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수 $k_1, k_2, \ldots, k_N$이 공백으로 구분되어 주어집니다.
출력 설명
필요한 최소 타워의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
3 8 2 1 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
탐욕법(Greedy)을 사용합니다. 현재 블록을 올릴 수 있는 타워들(즉, 맨 위 블록의 크기가 현재 블록보다 큰 타워들) 중에서, 맨 위 블록의 크기가 가장 작은 타워를 선택하여 올립니다.
타워들의 상단 블록 크기를 정렬된 상태로 유지하며 이분 탐색(
타워들의 상단 블록 크기를 정렬된 상태로 유지하며 이분 탐색(
upper_bound)을 사용하면 각 블록을 $O(\log N)$에 처리하여 전체 $O(N \log N)$에 해결할 수 있습니다.