[백준 3020] 개똥벌레

문제링크 : https://www.acmicpc.net/problem/3020

💻 문제 풀이 : C++

#### 🤣시간초과...

#include <iostream>

using namespace std;

int MAP[500010];

int main()
{
	int N, H;
	cin >> N >> H;

	int input;
	for (int i = 0; i < N; i++)
	{
		cin >> input;
		// 홀수 짝수 구분하기
		if (i % 2 == 0)
		{
			// MAP에 기록하기
			for (int h = 1; h <= input; h++)
			{
				MAP[h]++;
			}
		}
		else {
			// MAP에 기록하기
			for (int h = H; h > H - input; h--)
			{
				MAP[h]++;
			}
		}
		// 최솟값 + 수 기록하기
		int debug = 1;
	}

	int cnt = 0;
	int min = 234567890;
	for (int i = 1; i <= H; i++)
	{
		if (min > MAP[i]) {
			min = MAP[i];
			cnt = 1;
		}
		else if (min == MAP[i]) {
			cnt++;
		}
	}

	cout << min << " " << cnt << "\n";

	return 0;
}

정답

#include <iostream>

#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

int top[500010];
int bottom[500010];

int main()
{
	int N, H;
	cin >> N >> H;

	int input;
	for (int i = 0; i < N; i++)
	{
		cin >> input;
		if (i % 2 == 0)
			bottom[input]++;
		else
			top[H-input+1]++;
	}

	// 장애물의 개수
	for (int i = 1; i <= H; i++)
	{
		top[i] += top[i-1];
		bottom[H-i] += bottom[H - i + 1];
		// int debug = 1;
	}

	int cnt = 0;
	int min = 2134567890;
	for (int i = 1; i <= H; i++)
	{
		if (min > top[i] + bottom[i])
		{
			min = top[i] + bottom[i];
			cnt = 1;
		}
		else if (min == top[i] + bottom[i])
		{
			cnt++;
		}
	}

	cout << min << " " << cnt << "\n";

	return 0;
}

---

📌 memo 😊

---

ref)
👍
https://hyeo-noo.tistory.com/310