백준/1138번(Greedy)/C++

문제 설명

 

그리디 문제는 대부분 문제를 있는 그대로 받아들이기보다는, 문제에서 요구하는 바를 제대로 한 번에 구할 수 있는 방법을 간파해야 해서 까다롭다. 그게 한 번에 보이면 바로 풀리는데, 그렇지 않으면 이 문제처럼 계속 틀리게 된다.

 

 

디버깅 기록

: 작은 수부터 위치를 찾는다면, 아직 비어있는 위치는 자신보다 큰 수가 올 예정이라는 것을 알 수 있다. 따라서 맨 앞부터 훑으면서 아직 원소가 들어가 있지 않은 자리의 개수를 세어서 입력받은 수와 일치된 후에 원소를 삽입하면 된다. 작은 수부터 위치를 찾아야 한다는 점, 입력 위치를 찾는 수의 입장에서 아직 비어있는 자리는 내가 들어가지 않는 이상 나보다 큰 수가 위치할 자리라는 점을 파악해야 풀 수 있다.