Problem solving (2022/01/08)

SOLVED.AC 의 CLASS 7에 분류되어 있는 문제들 중 안푼 문제들을 조금 풀어보았다.

같은 탑 (BOJ#1126)

두 개의 탑을 쌓는데, 각 탑에 최소 블록 1개는 사용하면서 탑의 높이를 같게 만드는 경우 중, 가장 높게 만들 수 있는 경우의 높이를 구해야 한다. $N \leq 50$ 라는 제한에 주목해보자, 이 제한은 충분히 작기 때문에 이 문제를 DP로 해결할 수 있다는 희망을 준다.

결론부터 말하면, 다음과 같이 DP테이블 정의를 내리면 된다: $dp_{i,j}$ 는 $i$ 번째 블록까지 봤을 때, $(첫번째 탑의 높이)-(두번째 탑의 높이) = j$ 일 때, 첫번째 탑의 높이의 최댓값.

높이 차를 테이블의 인자에 저장하고 테이블의 값으로는 한 탑 (앞선 정의에선 첫번째 탑) 의 높이를 저장했다. 여기서 주의해야 할 점은, $i$ 번째 블록을 사용하지 않는 경우도 잘 고려하여 점화식 구현을 해야 한다는 것이다. 또, 답이 블록을 한번도 포함하지 않은 경우를 포함하지 않게 끔 적절히 구현하여야 한다. 답은 $dp_{N,0}$ 을 출력하면 된다 (탑의 높이 차가 음수가 될 수도 있어 음수인덱스의 접근을 막기 위해 배열칸을 $500,000$ 번 정도 쉬프트해서 사용하면 된다). 최종 시간 복잡도는 $O(N*10^6)$ 인데, 여기서 $10^6$ 은 가능한 모든 높이 차의 영역을 나타낸다. 이는 상수이므로 선형시간안에 문제를 풀었다고 우기고 싶지만... 그러기엔 너무나도 큰 오버헤드였다.

이 문제를 해결했다면, ICPC 2019 인예 문제인 Two Machines (BOJ#17528) 도 비슷하니 한번 풀어보자.

수열과 쿼리 1 (BOJ#13537)

그 유명한 수열과 쿼리의 첫번째 문제이다 (수열과 쿼리 0 문제가 있지만... 아무튼 이게 "첫"번째다).

쿼리의 종류는 하나다, $i, j, k$ 가 주어지면, $A_i, A_{i+1}, ..., A_j$ 에서 $k$ 보다 큰 원소의 개수를 출력하기만 하면 된다. 이 문제의 핵심은 오프라인 쿼리를 사용하는 것이다. 중간에 어떠한 업데이트 쿼리도 없기 때문에 이가 가능함은 간단히 보일 수 있다. 쿼리를 $k$ 기준으로 내림차순 정렬하고, 순차적으로 해결할 것이다. 세그먼트 트리를 사용하여 구간합 쿼리를 빠르게 처리할 것인데, 우선 처음에는 빈 세그먼트 트리로 시작한다. 내림차순으로 정렬한 쿼리의 $k$ 값을 $k_1, k_2, ... k_M$ 이라고 하자 ($k_1$이 제일 큰 값). 그리고 $k$ 값이 $k_i$ 인 어떤 쿼리를 해결하기 전에, $k_i$ 보다 큰 모든 A의 원소를 "업데이트" 한다. 여기서 업데이트란, 업데이트를 할 원소가 $A$ 의 $j$ 번째 원소라면, 세그먼트 트리의 $j$ 번째 칸을 1만큼 증가시킨다. 이런식으로 업데이트해야할 모든 원소를 업데이트 했다면 세그먼트 트리에는 $k_i$ 보다 큰 원소들의 구간 개수를 $O(N)$ 에 계산할 수 있을 것이다. 만약 쿼리가 $k$ 보다 작은 원소의 개수를 출력하는 문제였으면 쿼리는 오름차순으로 정렬되었어야 할 것이다. 따라서 모든 쿼리에 대해 위와 같이 수행하면 시간 복잡도는 $O(M log M + M log N)$ 이다 (쿼리 정렬도 포함하기 때문에).

총평

• 위 문제들은 확실히 전형적인 문제라는 느낌이 강했다. 연습문제로 나쁘지 않은듯.
• 위 문제들 말고도 격자판 채우기 (BOJ#1648) 이라는 흥미로운 문제도 해결했는데, 풀이를 적기에 내 능력과 (여백이) 모자라 적지 않는다.