https://www.acmicpc.net/problem/16496
문제 요약
- N개의 수가 주어짐(1천개, 0 ~ 1000000000)
- 숫자 순서를 적당히 섞어서 가장 큰 숫자 만들기
- 유사/응용 문제 https://www.acmicpc.net/problem/1422
접근법
- well-known 알고리즘이라고 하지만 도저히 증명이 안되어서 하나씩 접근해봄(결국 증명은 못함)
- 우선 예외부터 고려하면 전부 0이면 0으로 출력은 해야한다고 함. 이 부분은 적절히 처리 가능
- 앞자리가 9, 8, 7부터 오는것은 유리할 것임 => 앞자리가 9인 것들 모아서 처리, 8인 것들 모아서 처리, ... 여기까지는 쉽게 생각 가능
- 자 이제 9인 것들 그룹내에서는 어떻게 처리해야할까?
- 일단 두개만 있다고 보고 큰 것을 골라본다.
- 여러개가 있으면 모두 앞자리는 9니까 빼고 나머지로 그룹을 지어서 뭔가 하면 되지 않을까 하는 생각...
- 나머지 자리에 대해서 재귀적으로 처리.
- 981, 972 => 81, 72 => 981/927가 되니까 맞는것 같다
- 9, 93 => " ", 3 => 3인가 싶은데 93/9, 9/93이 되니까 뭔가 이상하다
- 37, 373 => " ", 3 => 3인가 싶은데 373/37, 37/373 이 되니까 이때도 이상하다
- 그럼 빈공간이 있으면 앞에 오는게 유리한가? 생각해보면
- 1, 13 => " ", 3 => 1/13, 13/1 ==> 아닌 것 같다
- 54, 542 => .. " ", 2 => 54/542, 542/54 ==> 맞는 것 같다
- 무조건 앞에오고 뒤에오는 건 아닌 것 같다
- 그런데 생각해보니 일단 가장 앞에 있는 숫자는 같은 것들 내에서 비교를 하는 것이니까, 빈 공간이 나오면 뒤에 그 숫자가 채워진다고 생각하면 되지 않을까?
- 7xxx 그룹들이 모여있다고 하면 어쨌든 저들은 (9그룹)(8그룹)(7그룹)(6그룹...) 7그룹 내부에서 적절히 정렬이 발생할 것이고
- 그룹에 가장 끝에 나열되는 것은 7xxx / 6xxx 꼴이 되니까 6xxx보다 앞서는 것은 일단 자명함
- 문제는 7xx, 7yyy 들끼리 누가 먼저냐 그런 의미
- 결과적으로 7xx/7yyy가 되었든 7yyy/7xx/7zzzz가 되었든 빈 자리에는 "7"이 채워지게 되니까 그렇게 접근해봄
- 사례를 생각해보자
- 9, 93 => 99, 93 => 9/93, 93/9 => 맞는 것 같음
- 87, 871 => 878, 871 => 87/871, 871/87 => 맞는 것 같음
- 12, 123 => 121, 123 => 123/12, 12/123 => 맞는 것 같음
- 37, 373 => 373, 373 => 37/373 > 373/37 같을때는 어떻게함????
- 31, 313 => 313, 313 => 313/31 > 31/313 같은데??
- 이러면 같을때는 또 조건을 추가해야하는데 무슨 조건인지 모르겠음
- 정리해보면
- 앞자리가 큰 것이 앞에오는게 유리
- 자리수가 같으면 큰 것이 앞에 오는 것이 유리
- 자리수가 다를때가 문제
- 빈 자리를 앞 자리로 채워서 비교해봐도 안되는 경우가 있음
- 숫자가 커졌다 작아졌다 패턴인지 이런 것을 비교해봐야하나...
- 이 시점에서 숫자 두개를 이어 붙여서 비교하는 방법이 추론이 되는 것 같다
- 그리고 이 방법이 왜 맞는지???? 증명이 어렵고
- 다른 풀이방법을 살펴보아도 증명에 대한 내용은 찾기 어렵다.
- 정렬에 대한 정합성은 고민하신 분도 있고, 의견을 주시는 분도 있다 : https://www.acmicpc.net/board/view/61621
newbieski