백준 23285 코멘트

알고리즘에 열정을 쏟던 시절, 풀이 수가 적은 문제의 해설을 구하기 어려워 학습에 많은 어려움을 겪었습니다. 빈약하지만 누군가의 짤막한 해설글을 통해 풀이를 유추해 나가던 기억이 납니다. 그 경험을 떠올리며, 누군가에게 도움이 되길 바라며 작은 힌트를 남겨봅니다.

 

 

N = 1000으로 꽤 작다. 시간에 대한 걱정 없이 풀어도 된다. 

 

두가지 방식으로 접근했다. 

 

1. 주어진 수열을 뒤에서부터 확인하여 트리를 복원하기

2. 주어진 수열의 앞에서부터 어떠한 방식으로 트리를 복원하기

 

그리고 이런 문제는 다양한 접근 방식을 통해 모든 풀이를 관통하는 절대 법칙을 찾는 것이 풀이에 유용하게 작용한 경험이 있다. 예를 들어, '가장 큰 수인 N은 항상 마지막까지 남는다' 이런 것들이다. 

 

처음은 1번 방식으로 접근했다. 이것이 자연스러운 흐름이라 생각했다. 예시와 함께 사고 흐름을 나열해 보자. 

 

10
5 5 3 6 3 4 9 4

 

트리는 최종적으로 2개의 정점과 1개의 간선의 모양을 갖는다. 이 예시에서는 4와 10이 마지막에 남는다. 

 

4 - 10

 

수열의 맨 뒤 숫자는 4이다. 이것을 트리에 반영하면 다음과 같다. 4에 a라는 수를 갖는 정점을 연결한다. 

 

a - 4 - 10

 

다음은 수열의 마지막에서 두번째 수인 9를 트리에 반영하자. 9는 기존 트리에 없던 수인데, 수열에 나타났다는 것은 a가 9라는 것을 알 수 있다. 그리고 9에 연결된 정점으로 b를 추가한다. 

 

b - 9 - 4 - 10

 

다음 수열의 마지막에서 세번째 수인 4를 트리에 반영하자. 미지수가 2개가 되었는데, b > c라는 대소 관계를 확인하고 넘어가야 한다. c가 더 작은 이유는, 더 먼저 트리에서 제거됐기 때문이다. 

 

b - 9 - 4 - 10
        |
        c

 

다음 수는 3이다. 3을 트리에 반영해야 하는데, b와 c 중에 어떤 것이 3일까? 좀 어렵다. 수열을 앞부분을 확인해야 명확히 알 수 있는데, 판단이 어렵고 구현이 어려워 보여서 풀이 방식을 바꿨다. 

 

2번 방식으로 접근해 보자. 수열의 앞부분부터 확인한다. 

 

10
5 5 3 6 3 4 9 4

 

처음 두 수는 5에 연결되어 있다. 그럼 다음과 같은 서브 트리가 있을 것이다. 

 

a - 5
    |
    b

 

세번째, 다섯번째 수는 3이다. 그럼 서브 트리를 만들 수 있다. 이런 방식으로 서브트리를 모두 만들면 5개의 서브트리가 완성된다. 

 

a - 5  c - 3  6  10 - 4 - f  9
    |      |  |       |      |
    b      e  d       h      g

 

a-g는 순서대로 삭제되는 정점이다. 여기에는 규칙이 있는데, 리프 노드이면서 리프 노드 중에 가장 작은 수이다. 1부터 10까지의 수 중에 리프 노드인 수와 아닌 수를 구분해서 관리해야 한다. 그 중 가장 작은 수를 매 시행에서 삭제한다. 

 

처음에 리프 노드인 수는 1, 2, 7, 8이다. a부터 순서대로 삭제할 것이고, 가장 작은 리프 노드는 1이기에 a = 1이다. 다음은 b 차례이고 자연스럽게 b = 2가 된다. 

 

5를 포함한 서브 트리를 보자. 앞선 2번의 시행에서 a, b는 제거된 상태이다. 그럼 5는 리프 노드가 된다. 3번째 시행 전 리프 노드는 5, 7, 8이다. 그러므로 c = 5로 결정된다. 이렇게 끝까지 진행하면 정답을 구할 수 있다.