알고리즘/acmicpc
1138
kwony
2015. 6. 25. 14:03
이 문제는 줄을 모두 비운 다음 입력에 따라서 하나씩 채워가면 된다.
예제로 나온 것을 보자
2 1 1 0
-1을 비어있는 것으로 보고 줄을 만들어보면
-1, -1, -1, -1
먼저 1의 크기를 가진 참가자는 자신의 앞에 두명이 있어야 한다.
그런데 다음으로 검사할 참가자들은 모두 1보다 키가 클 것이므로
앞에 두명을 비운 다음에 자신의 위치를 잡아 줄 수 있다.
-1, -1, 1, -1
다음 2의 크기를 가진 참가자는 자신 앞에 한명이 있어야 한다.
앞의 경우와 마찬가지로 다음으로 검사할 참가자들은 모두 2보다 키가 크기 때문에
3이 올지 4가 올지 생각하지 않고 그냥 앞에 한 칸을 비우면 된다
-1, 2, 1, -1
핵심은 키의 순서대로 적용하고 있다는 것이고
그 숫자만큼 빈칸을 만들어 두면 된다는 것이다.
처음에는 이 문제를 풀 때 무식하게 접근했는데
잘 생각해보니 쉽게 풀렸던 것 같다.