글 읽기 - 반례가 무엇이 있을까요?

isyou7487 3년 전 0

입력을 받아서

가장 높이가 큰 기둥의 L을 저장한후, 만약 2개 이상이라면 L이 작은 기둥의 L이 MaxLeft가 되고 큰 기둥의 L이 MaxRight가 됩니다.

넓이는 가장 높이가 큰 기둥을 기준으로 왼쪽, 자신, 오른쪽 총 3부분으로 나누어 구했으며

왼쪽넓이를 구할때는 index를 MaxLeft까지 훑으며 이전까지 구했던 최대높이보다 더 높은 기둥을 만나면 최대높이(tempH)를 갱신하고 넓이를 더하는 식으로 진행했습니다.

오른쪽넓이를 구할때는 indexing 순서를 바꾸어 왼쪽과 동일한 방법으로 구했습니다.

어디서 잘못된걸까요??

using System;
using System.Collections.Generic;

class Test
{
	static int N = 0;
	static int [] H = new int[1001];
	static int MaxHeight = -1;
	static int MaxLeft = -1;
	static int MaxRight = -1;
	
	public static void Main()
	{
		N = int.Parse(Console.ReadLine());
		string [] s;
		int l = 0;
		int h = 0;
		for(int i=0;  i<1001; i++)
		{
			H[i] = -1;
		}
		for(int i=0; i<N; i++)
		{
			s = Console.ReadLine().Split(' ');
			l = int.Parse(s[0]);
			h = int.Parse(s[1]);
			H[l] = h;
			if(MaxHeight < h)
			{
				MaxHeight = h;
				MaxLeft = l;
				MaxRight = l+1;
			}
			else if(MaxHeight == h)
			{
				if(MaxLeft < l)
					MaxRight = l+1;
				else if(MaxLeft > l)
					MaxLeft = l;
			}
		}
		int tempH = 0;
		int tempL = 0;
		int sum = 0;
		for(int i=1; i<=MaxLeft; i++)
		{
			if(H[i] > tempH)
			{
				sum+= (i-tempL) * tempH;
				tempL = i;
				tempH = H[i];
			}
		}
		sum += (MaxRight - MaxLeft) * MaxHeight;
		tempH = 0;
		tempL = 1000;
		for(int i=1000; i>=MaxRight-1; i--)
		{
			if(H[i] > tempH)
			{
				sum += (tempL - (i + 1)) * tempH;
				tempL = i+1;
				tempH = H[i];
			}
		}
		Console.WriteLine(sum);
	}
}

boylmm 3년 전 0

각 기둥의 L 위치를 저장해 두어야 정확한 면적 계산이 가능합니다.

예제 입력만 보아도, 입력값이 L 위치 순으로 정렬되어 있지 않으므로

기둥을 먼저 위치순으로 정렬한 후 접근하시면 좀 더 명확해지지 않을까요?

isyou7487 3년 전 0

앗 제가 설명이 부족했네요

H 라는 1001크기의 배열이 있을때

H[1]은 L이 1인 기둥의 높이를 저장하는 배열입니다.

입력을 다 받고나서 H를 1부터 탐색하면 L위치 순서대로 높이를 탐색하도록 구상했습니다.

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

문제

문제

출처

ICPC

반례가 무엇이 있을까요?

isyou7487 3년 전 0

boylmm 3년 전 0

isyou7487 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말