[BOJ] 백준 17028. Sleepy Cow Sorting (Silver IV)

슬슬 영어공부 및 토익을 준비할 때가 되기도 했고,

학교 교수님께서 알고리즘을 영어로 가르치시기 때문에 가끔씩 영어 문제를 풀면서 영어에 친숙해지는 시간을 가져보려고 한다.

그래서 푼 문제가 바로 이거다.

https://www.acmicpc.net/problem/17028

17028번: Sleepy Cow Sorting

문제 요약

Farmer John은 자신과 마주보고 있는 소에게만 위치를 옮기도록 지시할 수 있다.

소 위치를 옮길 때 제한은 없다.

최소한의 지시로 소 번호가 오름차순으로 정렬되도록 하여라.

---

의식의 흐름 및 해설

 

재밌는 USACO 문제다.

어떻게 이렇게 Farmer John 소재로 다양한 문제를 낼 수 있는지 궁금하다.

 

우선 Farmer John이 맨 왼쪽에 있으므로,

맨 왼쪽에 있는 소만 위치를 자유자재로 바꿀 수 있다.

그러므로, 맨 오른쪽에서 볼 때 내림차순으로 정렬돼있지 않은 소는 현재위치보다 오른쪽으로 옮겨주어야한다.

따라서 맨 오른쪽에서 볼 때 내림차순으로 정렬돼있는 sequence의 길이를 구해주면 된다.

---

코드

#include <bits/stdc++.h>
using namespace std;
int N, a[102], ans;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin>>N;
	ans=N-1;
	for(int i=0;i<N;i++){
		cin>>a[i];
	}
	for(int i=N-2;i>=0;i--){
		if(a[i]>a[i+1])
			break;
		ans--;
	}
	cout<<ans<<"\n";
}

---

Silver IV 치고는 좀 생각할 거리가 많다고 생각했는데,

지금 다시 보니까 S4가 적당한 티어인 것 같기도?

참고로 난 그리디 태그도 포함된다고 생각해서 그리디, 애드혹에 S3로 투표하였다.