https://www.acmicpc.net/problem/1129
이문제를 풀고나서 한 단어로 표현하면 '힘숨찐'이다.
처음엔 그냥 엥? 하고 아이디어가 매우 간단해 보여 이게 플레티넘 문제가 맞나 의심하며 풀었는데 역시나 어려운 문제였다.
방심하며 풀어서 오히려 멘탈이 털려 더 힘들지 않았나 싶기도 하다.
처음에 떠올린 아이디어는 우선 키를 오름차순으로 정렬 한다.
키가 1 2 3 4 5 6 7 있다고 하면 가장 작은 키 부터
1
2 3
4 5
6 7
이렇게 정렬 하는 것이다. 작은 수부터 한줄에 2개씩 순서대로 차곡차곡 쌓는 것이다.
이렇게 되면 1과의 차이가 최소가 될 수 있는 수는 일단 2, 그다음으로는 3 이다. 따라서 2번째 줄에 2,3을 둔다.
마찬가지로 남은 수들 중에 2와 붙을 수 있는 수는 4, 3은 5이다. (순서가 뒤바뀌면 키 차이의 최댓값이 더 커진다)
마지막으로 4와 인접한 6, 5와 인접한 7 로 끝이 난다.
(6,7 사이끼리는 정렬할 때부터 붙어있었으므로 -> 6,7사이의 차이 < Max키차이)
이런 식으로 구하면 두사람의 키 차이의 최댓값의 최소를 쉽게 구할 수 있다. 그러나 저것은 답이 아니다. 우리는 최댓값의 최소를 출력하는 것이 아니다.
키의 리스트 중 사전순으로 가장 앞에 있는 걸 찾아야 한다.
만약
1
2 3
4 5
57 58
이런식으로 있다고 치면 5, 57의 자리를 바꾸면
1
2 3
4 57
5 58
이렇게 해도 된다. 차이 최대값이 크다면 밑의 자잘한 수들의 차이는 조금 바뀌어도 되기 때문에 저렇게 순서를 변경할 수 있는 것이다. 그렇다면 어떻게 해야 할까.
이 문제에 대한 아이디어를 떠올리기 위해 또 고군분투가 시작되었다.
dp를 이용해 왼쪽 부분과 오른쪽이 가능한 부분 까지만 컷해서 바꿔치기를 할지... (차이의 최댓값을 만드는 포인트 다음부터는 바꿔치기가 불가능)
아래 처럼 1000 전까지는 1 2 5 3 7 까지 중에서는 왼쪽 오른쪽 끼리 바꿔치기 해도 상관없다.
1
2 3
5 7
8 10
1000 1002
1003 1005
아래와 같이 한줄로 통합하는 것이 가능하다. 그러나 이것도 최댓값이 매우 클 때만 가능하지, 최댓값이 고만 고만하다면 저렇게 통합하는 것도 마음대로 할 수 없다.
1
2
3
5
7
8 10
1000 1002
1003 1005
그런데 여기서, 지금 한 시도는 2줄을 한줄로 합치는 것이였다. 그럼 반대로 1줄을 2줄로 나누는 것은 어떨까.
사전순으로 가장 앞서는 것을 출력해야 하므로, 우선 정렬된 줄을 세운 후 오른쪽 줄로 숫자를 옮기는 것이다.
이때 유의해야 할 것은 최대한 가능하면 오른쪽으로 안보낼 수 있으면 안보내려고 애쓰는 것이다.
최대한 버텼다가 큰 수를 오른쪽으로 보내야 사전순으로 앞 설 수 있다.
여기서 최대한 버틴다는 것은.. 오른쪽 줄에서 우리가 방금전 구했던 차이의 최댓값이 안넘을 때까지 버티는 것이다.
방금전 배열을 한 줄로 세운다면
1
왼쪽줄 오른쪽줄
2
3
5
7
8
10
1000
1002
1003
1005
여기서 아까 구한 최댓값은 992이다. 가장 작은 수는 왼쪽줄, 오른쪽 줄에 모두 포함된다고 치자.
이제 2,3,5,7,. 쭉 가면서 오른쪽 줄의 차이가 992를 넘기전에 왼쪽에서 오른쪽으로 숫자를 보내며누 된다.
왼쪽줄에서 10을 넘어가면 1000부터는 차이가 999 (1과 1000) 을 넘어가므로, 10을 오른쪽으로 보내야 한다.
1
왼쪽줄 오른쪽줄
2
3
5
7
8
10
1000
1002
1003
1005
마찬가지로 1002를 넘기면 1003에서 1003 - 10 = 993 이 되므로 바로 전인 1002를 보내야 한다.
1
왼쪽줄 오른쪽줄
2
3
5
7
8
10
1000
1002
1003
1005
최종적으로 저렇게 완성이 되었다. 출력은 1,2,3,5,7,8,1000,1003,1005,1002,10,1 이런식으로 하면 될 것이다.
유의 할 점은 오른쪽줄로 숫자를 보낼때 왼쪽줄에서의 공백도 992(최댓값)을 넘기면 안된다는 것이다.
결론적으로 거쳐야 할 과정은
1. 고전적인(?) 방법으로 최댓값을 구하기.
2., 한줄로 쭉 세운후 최댓값을 안넘게 그리디하게 왼쪽으로 넘기기
이다. 아이디어 발상이 꽤나 참신하고 처음 떠올리기 쉽지 않았다.
앞으로 플레이상의 난이도인데 쉬우면 방심하지 말아야 겠다.
근데 실제 시험은 난이도를 모르고 접근하는 건데... 그냥 모든 문제를 방심하지 않는 습관을 들이는게 났겠다.
'알고리즘 > baekjoon(boj)' 카테고리의 다른 글
| [diamond4] [해설안봄,분류안봄,반례확인] 18939 경비병 세우기 게임 (0) | 2025.10.04 |
|---|---|
| [diamond5][해설안봄, 알고리즘 분류 확인] 2323 강강술래(담력테스트..) (0) | 2025.10.02 |
| [platinum4] [해설, 알고리즘 분류 안봄] boj1209 단조수열 만들기 (0) | 2025.09.29 |
| [diamond5][해설,알고리즘 분류 안봄] 18185, 18186 라면사기 (0) | 2025.09.26 |
| [platinum3][해설,알고리즘 분류 안봄] 1020 디지털 카운터 (0) | 2025.09.25 |