문제
농부 존은 멋진 사진을 찍기 위해 1…N(1≤N≤105)으로 번호가 매겨진 N마리의 소를 줄지어 세웠다.
처음에 소는 왼쪽에서 오른쪽으로 a1, a2, …, aN 순서로 배치된다.
농부 존의 목표는 왼쪽에서 오른쪽으로 b1, b2, …, bN 순서로 소를 배열하는 것이다.
이를 위해 일련의 수정 작업을 수행할 수 있는데, 각 수정 작업은 한 마리의 소를 왼쪽으로 일정 칸의 위치 이동하는 것이다.
농부 존이 소를 원하는 순서로 배열하는 데 필요한 최소 수정 횟수를 출력하는 프로그램을 작성하시오.
[부분문제]
테스트 케이스 1-6: N≤100.
테스트 케이스 7-10: N≤5000.
테스트 케이스 11-14: N≤100000.
입력
첫 번째 줄에는 N이 입력된다.
두 번째 줄에는 a1, a2, …, aN이 입력된다.
세 번째 줄에는 b1, b2, …, bN이 입력된다.
출력
소를 원하는 순서로 정렬하는 데 필요한 최소 수정 횟수를 출력하시오.
예제1
입력
5
1 2 3 4 5
1 2 3 4 5
출력
0
예제2
입력
5
5 1 3 2 4
4 5 2 1 3
출력
2
힌트
[예1]
이 예에서는 이미 정렬이 끝나있기에 수정 작업이 필요하지 않습니다.
[예2]
이 예에서는 두 가지 수정 작업으로 충분하다.
우선 4번 소를 왼쪽으로 네 칸 이동하고, 이어서 2번 소를 왼쪽으로 두 칸 이동하면 된다.
5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3
출처
USACO 2022 February Bronze
로그인해야 코드를 작성할 수 있어요.