백준 12841번: 정보대 등산 (C++)

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

12841번: 정보대 등산

 

풀이

기본적인 누적합 문제이다.

사실 바로 누적합 문제인지 알진 못했고 완전 탐색을 진행했을 때 시간복잡도가 10만 * 10만,

시간초과가 나올 듯 하여 경우의 수를 줄이는 방법을 생각하다보니 알게 되었다.

우선, 그림을 그려보니 위와 같은 식으로 테이블을 짤 수 있었다. 

 

빨간색이 지나는 부분을 다 더해주면 답을 구할 수 있다.

하지만 이 방법으로 하면 시간초과가 발생한다.

 

처음 횡단보도를 건넌다고 가정했을 때, right의 모든 값을 더하고

마지막 횡단보도를 건넌다고 가정했을때, left의 모든 값을 더한다는 것을 알았다.

 

만약 중간 횡단보도를 건너게 된다면,

left는 0부터 횡단보도까지의 거리의 합을 나타내고

right는 모든 값의 합에서 0부터 횡단보도까지의 거리의 합을 빼주면 되었다.

 

예를 들어, 두번째 그림과 같이 3번째 횡단보도를 건넜을 때, (6 + 5 + 2) - (5 + 2)를 해주면 6이 되고

이 값이 횡단보도를 건넌 위치에서 정보대까지 가는 거리가 된다.

 

 

그래서 각 항의 누적합을 이용한 배열을 만들었다,

두번째 횡단보도를 건널 때를 나타낸 그림인데

빨간 동그라미를 더하고 초록색 동그라미를 빼주면 총 거리를 구할 수 있다.

 

**left의 모든 값을 더했을 때, 10만 * 10만 = 100억이기 때문에 long long을 사용하자.

전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	long long left[100002] = { 0, };
	long long right[100002] = { 0, };
	int cross[100002] = { 0, };
	long long minDist = 1e18;
	int crossN = 0;

	cin >> N;

	for (int i = 0; i < N; i++)	cin >> cross[i];
	for (int i = 1; i < N; i++) {
		cin >> left[i];
		left[i] += left[i - 1];
	}
	for (int i = 1; i < N; i++) {
		cin >> right[i];
		right[i] += right[i - 1];
	}

	for (int i = 0; i < N; i++) {
		long long tmp = left[i] + cross[i] + right[N - 1] - right[i];
		if (minDist > tmp) {
			minDist = tmp;
			crossN = i + 1;
		}
	}

	cout << crossN << ' ' << minDist;
}