C++ / 3020 / 개똥벌레 ( 누적합 )

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

문제 요약

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔습니다. 동굴의 길이는 N미터이고, 높이는 H미터입니다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장합니다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴입니다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않습니다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴합니다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개입니다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말합니다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 됩니다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어집니다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성해야합니다.

 

문제 풀이

1. 장애물을 위에서 내려오는 장애물 밑에서 올라오는 장애물 2개로 구분하여 누적합으로 입력받습니다.

2. 입력받은 배열 2개를 누적합을 이용하여 개똥벌레가 부딪히는 총 장애물 수를 계산합니다.

3. 각 루트 별로 최소로 부딪히는 경우를 구합니다. 

4. 이전 값보다 작은 경우에 현재 값으로 초기화하고 그와 같은 경우를 세어줍니다.

5. 정답을 출력합니다.

주의할 점

위에서 내려오는 장애물은 h-현재 숫자 +1 에 저장해야합니다.

높이에서 뻬서 남는 칸이 부딪히지 않는 공간이기 때문입니다.

 

누적합 문제 풀어보다가 재미있게 푼 문제

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, h;



int up[500004];
int down[500004];
int cnt = 0;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> h;

	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;

		// 위에서 내려오는 장애물과 밑에서 내려오는 장애물 누적합
		if (i % 2 != 0)
		{
			up[a]++;
		}
		else
		{
			down[h - a + 1]++;
		}
	}

	// 누적합을 이용하여 개똥벌레가 부딪히는 총 장애물 수 계산
	for (int i = 2; i <= h; i++)
	{
		up[h + 1 - i] += up[h - i + 2];
		down[i] += down[i - 1];
	}
	int temp = 1e9;
	for (int i = 1; i <= h; i++)
	{
		// 현재 값보다 작은 경우
		if (temp > up[i] + down[i])
		{
			temp = up[i] + down[i];
			cnt = 0;
		}

		// 그 경우와 같은 경우의 개수

		if (temp == up[i] + down[i])
		{
			cnt++;
		}

	}
	cout << temp << " " << cnt;

	return 0;
}

예제 1

6 7
1
5
3
3
5
1

결과 1

예제 2

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

결과 2