RiseOJ – 제자리를 벗어난 소

설명

야심이 넘치는 농부 존은 늘 잘 안 되던 일에 도전하려 한다. 바로 소 떼 전체의 사진을 찍는 것이다.

사진이 보기 좋게 나오도록, 그는 소들이 키가 작은 순서부터 큰 순서대로 한 줄로 서기를 원한다. 안타깝게도 소들이 이렇게 줄을 서자마자, 언제나 말썽꾸러기인 소 베시가 줄에서 빠져나와 줄의 다른 위치에 다시 끼어들었다!

농부 존은 소 쌍들을 맞바꾸어 소 떼 전체가 다시 올바르게 줄을 서도록 하고 싶다. 이 목표를 달성하기 위해 소 쌍을 맞바꾸는 횟수의 최솟값을 구하는 것을 도와주자.

Problem credits: Brian Dean

제약

Problem credits: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ ( $2 \leq N \leq 100$ )이 주어진다. 다음 $$N$$ 개의 줄에 베시가 자리를 옮긴 후 줄을 선 소들의 키가 주어진다. 각 소의 키는 $1 \ldots 1,000,000$ 범위의 정수이다. 키가 같은 소가 있을 수 있다.

출력 형식

올바른 순서를 만들기 위해 농부 존이 소 쌍을 맞바꿔야 하는 최소 횟수를 출력한다. 맞바꾸는 두 소가 반드시 줄에서 인접해 있을 필요는 없다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 outofplace.in · 출력을 쓸 파일 outofplace.out

예제 1

입력

출력

설명

In this example, Bessie is clearly the cow of height 3. FJ return the cows to sorted order
using three swaps as described below:

2 4 7 7 9 3 - Original Lineup
2 4 7 7 3 9 - Swap the last two cows
2 4 3 7 7 9 - Swap the first 7 and 3
2 3 4 7 7 9 - Swap 4 and 3

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > January > Bronze

올림피아드 > USACO > 2017-2018 > January > Bronze

태그

JudgeUSACO

제자리를 벗어난 소

평가 및 의견

풀이 제출