(백준 2104번 부분배열 고르기 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 5탄

주말에 놀구 온 여파로 살짝 피곤하지만 새로운 출발이 신나는 월요일~

 

 포스팅은 여기에!↓

2024.01.12 - [알고리즘] - (백준 2447번 별 찍기 - 10 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 4탄

(백준 2447번 별 찍기 - 10 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 4

 

백준 2104번

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

2104번: 부분배열 고르기

 

과거의 내가 틀렸던 문제. 그런데 생각해보니 히스토그램 문제랑 비슷한거 같다는 생각이 들어 그 방법으로 풀어 보았다. 

 

//2104번 백준
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

// 부분배열 고르는 함수 - Histogram 문제와 비슷
// [s, e)
long long SubArray(long long* Arr, long long s, long long e) {
	if (s == e) return 0;
	if (s + 1 == e) return (long long) Arr[s]* Arr[s];
	long long mid = (s + e) / 2;

	long long result = SubArray(Arr, s, mid) > SubArray(Arr, mid, e) ? SubArray(Arr, s, mid) : SubArray(Arr, mid, e);
		
	//	max(SubArray(Arr, s, mid), SubArray(Arr, mid, e));
	// s : sum , m : minimum 의미
	long long l = mid, r = mid, m = Arr[mid], sum = Arr[mid];
	while (r - l + 1 < e-s) {
		long long p = s < l ? (long long)(sum + Arr[l - 1]) * min(m, Arr[l - 1]) : -1;
		long long q = r < e-1 ? (long long)(sum + Arr[r + 1]) * min(m, Arr[r + 1]) : -1;

		if (p>= q) {
			m = min(m, Arr[l - 1]);
			sum += Arr[l - 1];
			l--;
		}
		else {
			m = min(m, Arr[r + 1]);
			sum += Arr[r+1];
			r++;
		}
		if ((long long)m * sum > result) result = (long long) m * sum;
	}
	return result;
}
int main() {
	long long N;
	scanf("%lld", &N);
	long long *Arr = new long long[N];
	for (long long i = 0; i < N; i++) scanf("%lld", &Arr[i]);

	printf("%lld", SubArray(Arr, 0, N));

	delete[]Arr;
	return 0;
}

 

참고로 히스토그램 풀이는 라이님 풀이를 거의 외우다시피 쓰고 있는데, 엄청 깔끔하게 잘 짜서 혹시 참고 풀이가 없는 분들은 이 분의 풀이를 템플릿(template ㅋㅋ 복습했찌롱!)삼아 쓰셔도 진짜 좋읗 것 같다.

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220776241154&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

분할 정복(Divide and Conquer) (수정: 2016-12-25)

 

이건 어제밤 고분분투한 나의 흔적...

결론부터 말하자면 오 버 플 로 우 때문에 이렇게 되었다. 

디버깅으로 찾은 오류는

1. r < e-1까지 고려해주어야 할 부분을 r < e까지 고려

2. <algorithm>을 include 해줘야 max 와 min을 쓸 수 있는데 <utility>를 include함

3. 오 버 플 로 우

4. 오버플로우가 너무 화가나서 모든 걸 long long으로 바꾸다가 그만...

^^ int main부분도 바꿔버렸습니다..ㅎㅎ

 

그래도 오늘을 끝으로 분할정복 알고리즘을 나름 마무리 지을 수 있어서 뿌듯하다. 이번주에는 DP를 뽀개보도록!