Lucky Lucky Number

문제: LUCKYNUM / 그리디(탐욕적인 방법)

[ 해결책/후기 ]

 

문제를 보자마자 떠오르는 생각은 주어진 입력으로 구성된 모든 숫자를 만들고 그 숫자 중에서 정답을 찾는 것이다.

 

그러나 최대 200자리까지 입력되는데 이 방법을 썼다가는 TLE가 뻔하다. OTL

 

그러니 다른 접근 방법을 찾아야하는데 내가 접근한 방법은 lucky number에 가까운 수를 만들어가는 것이었다.

 

예를 들면 k=6일때 입력 값 n중에서 6이 입력되었는지 살펴보고 6을 먼저 찜하는 것이다.

 

이 경우, 첫 자리 수를 6을 선택하면 최선의 선택이 되기때문이다. (6이 또 있으면 역시 다음자리 수로 6을 선택하는 것이 최선이다.)

 

또 이런 생각도 해볼 수 있다.

 

k=6이고 6은 입력 된 숫자에 없고, 5와 7이 입력값에 있을 경우, 후보숫자가 두 개 존재하게 된다.

 

5로 시작하는 숫자집합과 7로 시작하는 숫자 집합이 그것이다.

 

이런 경우는 어떻게 될까?

 

생각해보면 5로 시작하는 숫자집합이 정답이 되려면 최대한 666...과 가까워야 하므로 5 이후의 숫자는 내림차순 정렬되야 한다.

(즉 큰 숫자들이 5이후에 배치 되어야 차이 값이 작아진다)

 

마찬가지로 7로 시작하는 숫자집합이 정답이 되려면 최대한 666...과 가까워야 하므로 7 이후의 숫자는 오름차순 정렬되어야 한다.

 

이렇게 접근해보면 입력 값에 따른 분류를 아래와 같이 나눌 수 있다.

 

1) 입력 되는 숫자 중 가장 큰 수가 k보다 작거나 같다 ---> 입력 값을 내림차순 해버리면 끝난다.

 

2) 입력 되는 숫자가 모두 k보다 큰 경우 --> k보다 크면서 k와 가장 가까운 수를 앞에다 놓고 나머지 수는 오름차순으로 정렬하면 끝.

 

3) k보다 작은 값과 큰 값이 섞여있는 경우 --> 좀 골치 아프다.

 

k=6인 경우, 입력된 숫자 중에 5와 7이 모두 있다면 5로 시작되는 숫자집합을 만들고 7로 시작되는 숫자집합을 만든다.

(만약 7이 있고 5는 없는 경우, 정답은 7로 시작되는 숫자집합이 될 것이므로 비교적 쉬운 경우라고 볼 수 있다)

 

5로 시작되는 숫자집합은 내림차순정렬, 7로 시작되는 숫자집합은 오름차순정렬 한다.

 

이렇게 만들어진 숫자집합 중 6666...(lucky number)과 가까운 수가 무엇인지 따져봐야 한다.

 

막연하게 생각해보면 최악의 경우 입력된 길이가 200이면 어떻게 크기 비교를 해야할지 막막해진다.

 

증명할 수는 없지만 나는 몇 자리 비교해보면 금방 어떤 수가 lucky lucky number인지 판별이 가능하겠다고 직감했다.

 

왜냐하면 k보다 작은 수로 시작되는 숫자집합은 첫 자리 이후에 내림차순으로 정렬되어 있고

 

k보다 큰 수로 시작되는 숫자집합은 첫 자리 이후에 오름차순으로 정렬되어있기 때문에

 

lucky number와 이 두 숫자집합의 차이가 계속 같을 수가 없어보였기 때문이다.

 

그래서 만들어진 두 숫자집합의 앞자리부터 lucky number(kkk....)와 비교해가면서 정답을 찾았다.

[출처] [AOJ 문제] Lucky Lucky Number|작성자 DevMoon

코드: https://github.com/xgate/algospot/blob/master/GREEDY/LUCKYNUM.cpp