27979. 볼링장 아르바이트

친구가 학교 대회에서 낸 문제이다. 

27979번: 볼링장 아르바이트

---

공을 뺄 때는 어디에서나 뺄 수 있지만, 넣을 때는 맨 앞에만 넣을 수 있다. 주어진 정수를 오름차순으로 정렬하려면 공을 최소 몇 번 빼야 하는지 구하면 된다.

 

어디선가 많이 본 세팅인데.. LIS 문제인가 싶어서 생각해 봤으나 아니었다. 정렬 말고는 딱히 알고리즘은 없는 듯하다.

 

예제를 관찰한 결과, $i$번 공 앞에 $i$번 공보다 큰 공 $j$가 있다면

1. $i$번 공과
2. $k<i$이면서 $w[k]<w[i]$인 공 ($i$보다 앞에 있으면서 $i$번 공보다 가벼운 공 $k$)

을 모두 움직여야 한다. $j<i$이고 $w[j]>w[i]$인 $(i,~j)$ 쌍이 존재한다면 $i$번 공을 앞으로 옮겨야 한다. 그런데 $i$번 공을 앞으로 옮기면 $k<i$이고 $w[k]<w[i]$인 $k$번 공($i$보다 앞에 있으면서 $i$번 공보다 가벼운 공) 역시 앞으로 옮겨야 한다. $i$번 공이 움직임에 따라 정렬이 깨졌기 때문이다.

 

위 조건을 만족하는 인덱스의 개수를 세면 된다. 의외로 구현이 까다로우니 주의.

---

될 듯 말 듯 해서 2시간 썼는데.. 이런 걸 30분 안에 풀어야 하는데. 쩝.