codeup 3095 돌진 c++ 풀이

각 통나무에서 시작하는 지점을 1, 끝나는 다음지점(끝나는 지점도 포함되기 때문)을 -1로 두겠습니다.

그러면 위에 사진처럼 1 ~ 8번 인덱스는 각 1 1 0 -1 0 0 0으로 정의할 수 있습니다. 그런 다음 순차적으로 값을 더하여 가장 큰 max값을 찾아서 출력하면 되는 문제입니다.

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

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); //cin의 속도를 더 빠르게 하기 위해 사용

	vector<int> vec(10000000);
	int lineNum, max = 0;
	int x1, x2, y1;
	int checkMin = 10000001, checkMax = 0;

	cin >> lineNum;

	for (int i = 0; i < lineNum; ++i)
	{
		cin >> x1 >> x2 >> y1;

		if (checkMin > x1) //통나무에서 가장 작은 지점을 찾음
			checkMin = x1;
		if (checkMax < x2) //통나무에서 가장 큰 지점을 찾음
			checkMax = x2;

		//통나무에서 시작하는 지점을 +1
		vec[x1] += 1;
		//통나무에서 끝나는 다음 지점을 -1
		vec[x2 + 1] -= 1;
	}

	int check = 0;
	//통나무 중에서 가장 작은 지점부터 통나무 중에서 가장 큰 지점까지(단 마지막 지점에서 시작하지는 않으니 <)
	for (int i = checkMin; i < checkMax; ++i)
	{
		//누적합
		check += vec[i];

		if (max < check)
		{
			//최대값 정의
			max = check;
			//최대값이 현재 라인보다 같거나 크면 또는 남은 반복문을 다 더한다 해도 max값을 
			//못 넘기면 break하여 속도 향상
			if(max >= lineNum || check + (checkMax - (i + 1)) <= max) break;
		}
	}

	//Max값 출력
	cout << max;
}

---

후기

처음 풀 때는 map을 이용하여 각 통나무에서 범위를 누적하여 문제를 해결할려고 했지만 메모리 초과가 나가지고 이 방법으로 해결 할 수 없었다. 그래서 vector도 이용해보고 배열도 사용했지만 계속 시간초과가 나왔다. 다만 결국에는 오랜 시간 동안 생각 한 끝에 위 로직을 생각하여 문제를 풀게 되었다.