Informatica Online Judge

  Sorting a Three-value (3 정렬, IOI-96) [0272 / 0110]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 46   Total Tried : 191


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

정렬이라는 주제는 컴퓨터과학에서 가장 유명하고 잘 알려진 문제 주제들 중 하나이다.

이 문제에서는 특별한 정렬을 제안해본다. 이번 문제에서는 오직 3개의 키 값만 가지고 정렬을 하고자 한다.

일반적으로 올림피아드 등의 대회에서는 금메달, 은메달, 동메달의 3가지 값만 있다. 이 3값을 정렬하는 것도 3개의 값을 정렬하는 것이다.

여러분에게 N개의 1, 2, 3으로 이루어진 수열이 주어진다. 어려분은 이 수열을 비내림차순으로 정렬하는 것이 목적이다.

단, 여기서 허용된 연산은 두 수의 위치를 바꾸는 행위 뿐이다.

임의의 1, 2, 3으로 이루어진 수열이 주어질 때, 이 수열을 비내림차순으로 정렬하는데 필요한 최소횟수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 자료의 수를 나태내는 정수 N이 주어진다. (단 N은 1000이하의 자연수)
다음 줄 부터 N줄에 걸쳐서 1, 2, 3 중 하나의 수가 주어진다.

Output

비 내림차순으로 정렬하는데 필요한 최소 교환 횟수를 출력한다.

IO Example

입력
9
2
2
1
3
3
3
2
3
1

출력
4

IOI(International Olympaid in Informatics) - 1996기출

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]