백준 2812. 크게 만들기

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

2812번: 크게 만들기

 

기본적인 아이디어는 주어진 숫자들을 앞에서부터 탐색하면서 현재 숫자보다 작은 앞의 수들을 밀어내는 것이다.

예를들어 주어진 숫자가 다음과 같다면 

4177252841

처음에 4가 있다.  // 4 

 

그 후 1이 오는데 앞의 수인 4보다 작으므로 그냥 붙인다. // 41 

 

그 후 7이 오는데 앞의 수인 1 보다 크다.  1을 지운다. 

앞의 수인 4보다 크다. 4를 지운다. // 7 

 

그 후 7이 오는데 앞의 수인 7보다 작거나 같으므로 그냥 붙인다. // 77 

 

그 후 2가 오는데 앞의 수인 7 보다 작거나 같으므로 그냥 붙인다. // 772

 

.. 

 

이런 식으로 현재 탐색하는 숫자보다 작은 숫자들을 지워나가면 된다.

그런데 이런식으로 하다보면 앞에 있는 모든 숫자들보다 큰 수가 와서 앞의 숫자들을 다 지워버렸을때, 남은 숫자들을 다 붙여도 목표하는 숫자의 갯수보다 모자랄수가 있다. 

따라서 무작정 숫자들을 지워버리면 안되고 (현재까지 모은 숫자들) + (남은 숫자들)이 목표 숫자의 수 이상일때만 지워야한다.