[2243] 사탕상자

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

2243번: 사탕상자

세그먼트트리 문제다. 접근방법이 떠오르지 않아 풀이를 찾아보았다.

 

풀이

1번 맛부터 1,000,000번 맛에 해당하는 사탕의 개수를 표현하는 세그먼트트리를 생성한다. 최대합 세그먼트 트리를 구현하면 된다.

 

고민할 부분은 문제의 요점인 i번째 순번의 사탕을 찾는 것인데, 해당 부분도 재귀호출을 통해 접근해야 한다. 부모노드부터 시작하여 좌측자식으로 탐색할지 우측자식으로 탐색할지 결정해야 한다. 만일 좌측노드의 값이 i이상이라면, 즉 좌측 노드에서 i번째 사탕을 찾을 수 있다면 그대로 좌측노드로 탐색을 시작하면 되고, 만일 좌측노드의 값이 i 보다 작다면, 즉 좌측노드에서 i번째 사탕을 찾을 수 없다면 우측노드로 탐색을 시도해야 하는데, 우측노드를 탐색한다는 뜻은 (i - 좌측노드의 값) 번째 사탕을 찾는다는 의미이다. 문제에서 현재 없는 사탕을 찾는 경우는 주어지지 않으므로 리프노드에 도달할 때까지 찾아야 할 사탕의 순번을 조절해서 탐색을 시도하면 된다.

 

예제를 기준으로 설명하면 다음과 같다.

0으로 초기화된 세그먼트 트리 생성 예제의 경우 큰 번호의 사탕이 나오지 않았기에 6번까지의 범위만 그렸다.

 

1번 사탕 2개 추가. 3번 사탕 3개 추가.

 

두 번째로 맛있는 사탕을 찾는다. 1번이 두 개 있기에 1번을 반환. 방문하는 모든 좌측노드가 2 이상이기에 1번 사탕까지 바로 접근. 사탕을 빼내는 작업이기에 방문한 리프노드에 도달할 때까지 방문한 모든 노드는 1만큼 차감해 준다.

 

이번에도 두 번째로 맛있는 사탕을 탐색, 0-3 범위에 도달할 때까지는 노드 값이 4이기에 좌측 노드 탐색.

이후에는 좌측 노드의 값이 1이므로 해당 노드에는 두 번째로 맛있는 사탕을 찾을 수 없다. 따라서 우측 노드 탐색 수행.

우측에서는 전체 범위에서 두 번째로 맛있는 사탕을 찾기 위해선 해당 범위에서 첫 번째로 맛있는 사탕을 찾아야 하기에 순번을 1로 변경하여 탐색을 진행하면 된다. 마찬가지로 방문했던 노드는 1 차감한다.

 

1번 사탕의 개수 변동. 마찬가지로 리프노드를 만날 때까지 변경 값을 반영하면 된다.

 

마지막으로 두번째로 맛있는 사탕 탐색. 위에서 탐색한 방법과 같은 방법으로 탐색 후 3번을 반환 후 방문했던 노드의 값 1을 차감한다.

 

정답 코드