[중등부] 2024 KOI 2차대회 대비 모의고사 (1주차)

러시아 전통 인형은 속이 비어있기에 보다 크기가 작은 인형이 그 안에 들어갈 수 있다.

책상 위에 N개의 러시아 전통 인형이 있다.

i번째 러시아 전통 인형의 크기는 A_i다. (1 \le i \le N)

i번째 러시아 전통 인형 안에 j번째 러시아 전통 인형을 넣기 위해서는 아래 조건이 충족되어야 한다. (1 \le i,j \le N)

• i \neq j

• A_i > A_j

• i번째 러시아 전통 인형의 속에 다른 인형이 들어있지 않다.

하나의 인형을 다른 하나의 인형에 넣게 되면 책상 위에 남아 있는 러시아 전통 인형의 수가 한 개 줄어든다.

하나도 겹쳐져 있지 않은 상태의 인형들의 개수와 크기가 주어졌을 때, 이를 포개어 정리하였을 때 책상 위에 남아있을 수 있는 러시아 전통 인형의 최소 개수를 출력하는 프로그램을 작성하시오.