[BOJ 18251] 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

백준 18251번 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

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

18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

---

문제

포화 이진 트리에 노드가 2 ^ k - 1개 만큼 존재한다

적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하려한다

가중치의 최대 합은?

---

풀이

스위핑 알고리즘으로 이 문제를 풀 수 있습니다.

 

문제에서 주어진 입력 예제를 그림으로 표현해보겠습니다.

 

루트노드부터 dfs를 돌려 중위 순회 순으로 출력하면 각 노드의 x좌표가 나옵니다.

그리고 y좌표는 트리의 높이로 생각해볼 수 있습니다.

 

트리 상의 모든 노드를 2차원 상의 좌표 평면으로 나타낼 수 있습니다.

 

그럼 2차원에서 적당한 직사각형을 그려 가중치의 최대 합을 구하는 문제로 바꼈습니다.

---

이 문제는 포화 이진 트리이기 때문에 문제가 조금 쉬워지는 부분이 있습니다.

바로, y 좌표의 범위가 [1, log(N+1)]을 만족한다는 점입니다.

 

직사각형의 높이, 즉 y좌표의 범위 [y1, y2]를 설정해준다면

직사각형의 너비만 적당히 선택해서 가중치의 최대 합을 구할 수 있습니다.

 

만약 정답이 되는 직사각형의 너비 [x1, x2]를 정했다면,

노드의 좌표가 [x1, x2], [y1, y2] 사이에 있는 노드는 모두 포함해야 한다는 소리입니다.

 

즉, [y1, y2] 사이에 포함되는 노드들 중 최대 가중치 연속부분 수열 (Maximum SubArray) 을 찾아주면 됩니다.

 

[y1, y2]는 이중 반복문으로 하나씩 살펴보면 됩니다.

=> O(logN * logN)

---

실제 예제와 함께 자세히 살펴보겠습니다.

 

아래 케이스는 [y1, y2]가 [1, 3]인 모습입니다.

(루트 노드의 높이가 1, 리프 노드의 높이를 4로 두었습니다.)

 

빨간색 직사각형 안에서 실제 최대 가중치 합을 가지는 직사각형의 너비를 구해주면 됩니다.

 

노드를 다 추출해서 1차원 배열에 넣어보겠습니다.

여기서 최대 가중치를 가지는 연속 부분배열은 아래와 같습니다.

직사각형의 높이가 [1, 3]에서는

최대 가중치를 가지는 직사각형은 8, 0을 포함하고

그 합은 8이 됩니다.

 

이를 트리 상에서 다시 그림으로 표현하면 아래와 같습니다.

---

실제 정답 직사각형의 높이인 [2, 4]에서 진행해보겠습니다.

 

여기서 최대 가중치 부분 수열은 아래와 같습니다.

직사각형의 높이만 정해진다면, 해당 높이 안에 들어가는 노드들 중 maximum subArray를 찾아주면 된다는 것을 알게됐습니다.

---

높이를 정하는 이중 반복문이 O(logN * logN) 만큼 걸립니다.

하지만 maximum subArray를 찾는데 오래 걸리면 결국 시간 초과를 마주하게 됩니다.

어떻게 빨리 찾을 수 있을까요?

 

여기서 스위핑 기법을 사용할 수 있습니다.

저희는 조건을 만족하는(=가중치의 합이 가장 큰) 연속하는 부분수열을 찾으면 됩니다.

 

연속하는 부분 수열이기에, i번째 노드를 확인할 때 아래 2가지 중 더 큰 값을 가져오면 됩니다.

• i-1 번째 노드를 포함하는 연속 부분수열의 최대 가중치 합 + i번째 노드의 가중치
• i번째 노드의 가중치

바로 직전 노드를 포함하는지, 아닌지 여부만 확인해주면 됩니다.

 

아래는 find maximum subArray 과정을 그림으로 나타낸 모습입니다.

이 중 가장 큰 가중치의 합만 구해주면 됩니다.

8, 10, 0, -1, 7을 포함할 때 가중치가 가장 크고 정답은 24입니다.

 

반복문 1번에 정답을 찾을 수 있기에 시간 복잡도는 O(N) 입니다.

 

최종 시간복잡도는 O(logN * logN * N) 입니다.

---

코드

#include <cstdio>

#define max(a, b) ((a) > (b) ? (a) : (b))

const int SIZE = 1 << 18;
typedef long long ll;

struct Info {
	int value, height;
}info[SIZE];
int arr[SIZE];

int N, dfsCnt = 0;
void dfs(int n, int height) {
	int left = n << 1, right = n << 1 | 1;
	if (left <= N) dfs(left, height + 1);

	info[dfsCnt++] = { arr[n], height };

	if (right <= N) dfs(right, height + 1);
}

ll findMaxSubArr(int h1, int h2) {
	ll ret = -1e9;
	ll cur = 0;

	for (int i = 0; i < N; ++i) {
		if (info[i].height < h1 || info[i].height > h2) continue;
		cur = max(cur + info[i].value, info[i].value);
		ret = max(ret, cur);
	}

	return ret;
}

ll solve() {
	dfs(1, 1);
	ll ret = -1e9;

	for (int h1 = 1; 1 << h1 <= N + 1; ++h1) {
		for (int h2 = h1; 1 << h2 <= N + 1; ++h2) {
			ret = max(ret, findMaxSubArr(h1, h2));
		}
	}

	return ret;
}

int main()
{
	//freopen("input.txt", "r", stdin);

	scanf("%d", &N);
	for (register int i = 1; i <= N; ++i)
		scanf("%d", &arr[i]);

	printf("%lld\n", solve());
}