글 읽기 - 6549번 분할정복

leehanjun 7년 전 0

분할 정복을 이용하여 풀려고 했습니다.

그런데 TEST CASE에선 잘 작동했는데 제출 시 틀렸습니다.

코드에서 잘못 된 건지, 아니면 알고리즘이 잘 못 된 것인지 모르겠습니다.

/*
 * 6549번 - 히스토그램
 */

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

/*
 * Get maximum area of histogram by using Divide & Conquer.
 */
 
vector<long long> g_histogram;

long long
get_max_area (unsigned a_low, unsigned a_high)
{
	// Base Case:
	if (a_low == a_high)
	{
		return		g_histogram[a_low];
	}
	
	unsigned mid, idx_left, idx_right;
	long long ret, height, area, single;
	
	mid = (a_low + a_high) / 2;
	idx_left = mid;
	idx_right = mid + 1;
	height = min (g_histogram[idx_left], g_histogram[idx_right]);
	ret = area = (idx_right - idx_left + 1) * height;
	
	while (a_low != idx_left || a_high != idx_right)
	{

		if (idx_left == a_low)
		{
			++idx_right;
			height = min (height, g_histogram[idx_right]);
			area = (idx_right - idx_left + 1) * height;
			ret = max (ret, area);
		}
		
		else if ( idx_right == a_high)
		{
			--idx_left;
			height = min (height, g_histogram[idx_left]);
			area = (idx_right - idx_left + 1) * height;
			ret = max (ret, area);
		}
		
		else
		{
			unsigned idx_temp;
			
			// Algorithm: Get promising index
			idx_temp = g_histogram[idx_left] >= g_histogram[idx_right] ? --idx_left : ++idx_right;
			height = min (height, g_histogram[idx_temp]);
			area = (idx_right - idx_left + 1) * height;
			ret = max (ret, area);
		}
		
	}
		
	single = max ( get_max_area (a_low, mid), get_max_area(mid + 1, a_high) );
	return 	ret = max (ret, single);
	
}

vector<long long>
set_histogram (int N)
{
	vector<long long> histogram;
	long long value;
	
	for (int cnt=1; cnt <= N; ++cnt)
	{
		cin >> value;
		histogram.push_back (value);
	}
	
	return histogram;
}

int
main ()
{
	int N;
	
	cin >> N;
	
	while (N != 0)
	{
		
		g_histogram = set_histogram (N);
		cout << get_max_area (0, g_histogram.size () - 1) << endl;
		cin >> N;
		
	}
	
	
}

leejk9592 7년 전 1

4달 전에 질문이 올라왔는데 답변이 없군요, 누구나 다른 사람의 소스는 설명이 없으면

파악 하기도 힘들꺼라 생각하고, 위 소스를 읽어봐도 저도 잘 모르겠습니다...

보통 이럴 때 저는 Brute Force 방식으로 결과를 내는 소스를 하나 작성해서

시간 내로 실행 가능하게 제한된 입력을 무작위로 난수 생성 해서

두 소스의 출력을 비교해 보는 식으로 해결하곤 한답니다

도움이 되기를...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

6549번 분할정복

leehanjun 7년 전 0

leejk9592 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말