백준 - 빗물(c++)

문제 : https://www.acmicpc.net/problem/14719

14719번: 빗물

문제설명

1. 푸는 방법이 굉장히 많다. 어떤 방법으로 푸느냐에 따라 난이도가 달라지는 것 같다.

 

알고리즘

1. 먼저 가장 높은 위치를 구한 뒤 왼쪽과 오른쪽으로 나눠 생각한다.

2. 왼쪽부터 가장 높은 위치 인덱스 까지 반복문을 진행한다. 조건은 최대값인 tempValue 보다 현재위치의 높이가 크거나 같을 때 최대인덱스인 tempIdx부터 현재 위치까지 반복문을 진행하며 result에 높이를 더해준다.

3. 오른쪽도 2번과 같이 진행한다.

주의사항

1. 다른 풀이를 찾아보니 왼쪽부터 스캔해가며 반복문을통해 현재 인덱스의 물 높이를 구하는 방법을 많이 사용한다. 내가 푼 방법이랑 비교했을 때 속도는 비슷하지만 다른 풀이가 좀 더 가독성이 좋은 것 같다.

 

구현

int map[501];

int main()
{
	int H = 0,W = 0;
	scanf("%d %d", &H, &W);
	int maxValue = 0,maxIdx = 0;

	for (int i = 0; i < W; i++)
	{
		scanf("%d", &map[i]);
	}

	//제일 높은 위치 구하고 왼 오로 나눔
	for (int i = 0; i < W; i++)
	{
		if (maxValue < map[i])
		{
			maxIdx = i;
			maxValue = map[i];
		}
	}

	int tempValue = map[0];
	int tempIdx = 0;
	int result = 0;

	for (int i = 1; i <= maxIdx; i++)
	{
		if (tempValue <= map[i])
		{
			for (int j = tempIdx+1; j < i; j++)
			{
				result += tempValue - map[j];
			}
			tempValue = map[i];
			tempIdx = i;
		}
	}

	tempValue = map[W-1];
	tempIdx = W-1;

	for (int i = W-2; i >= maxIdx; i--)
	{
		if (tempValue <= map[i])
		{
			for (int j = tempIdx - 1; j > i; j--)
			{
				result += tempValue - map[j];
			}
			tempValue = map[i];
			tempIdx = i;
		}
	}

	printf("%d", result);
	return 0;
}