[BOJ/Silver 3] 백준 12841 정보대 등산(C++)

문제 링크

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

12841번: 정보대 등산

 

문제

숭실 대학교 정보 과학관은 숭실 대학교 건물 중 제일 높은 곳에 있다. 민주는 평소에 버스를 타고 이 언덕을 오르지만, 이 문제에 등장하기 위하여 오늘 하루만 걸어서 올라간다.

정보 과학관을 오르는 길은 왼쪽 길과 오른쪽 길이 있다. 민주는 처음에 왼쪽 길 맨 아래에 있고 정보 과학관을 오른쪽 길 맨 위에 있다.

정보 과학관을 오르는 길은 매우 구불구불하다.

또, 길의 중간 중간에는 횡단보도가 있다. 민주는 횡단보도를 한번만 건널 수 있다.

최소한으로 걷기 위해서 민주가 건너야 하는 횡단 보도의 번호와 걸어야 할 거리를 구해 더운 여름 민주를 도와주자!

입력

첫 번째 줄에는 지점의 개수 n 이 주어진다. (2 ≤ n ≤ 100,000)

횡단보도는 1번 지점부터 n 번 지점까지 한 개 씩 있고, 왼쪽 1번 지점에는 민주가, 오른쪽 n 번 지점에는 정보 과학관이 위치한다.

• 다음 줄에는 i 번째 지점에 있는 횡단보도의 거리 (0 < cross ≤ 100,000) 가 주어진다. (1 ≤ i ≤ n)
• 다음 줄에는 i 번째 지점에서 i+1번째 지점까지 왼쪽 길의 거리 (0 < left ≤ 100,000) 가 주어진다. (1 ≤  i ≤ n-1)
• 다음 줄에는 i 번째 지점에서 i+1번째 지점까지 오른쪽 길의 거리(0 < right ≤ 100,000) 가 주어진다. (1 ≤  i ≤ n-1)

출력

민주가 최소 길로 가기 위해 건널 횡단보도는 몇 번째 지점에 있는지 출력하고, 민주가 최소 길로 가기 위해 걸어야 하는 거리를 출력한다.

만약, 최소 거리로 갈 수 있는 지점이 여러곳이라면 번호가 낮은 지점을 출력한다.

예제 입력 1

4
2 3 1 4
1 2 3
2 5 6

예제 출력 1

3 10

알고리즘 분류

• 브루트포스 알고리즘
• 누적 합

풀이

왼쪽 길의 거리의 누적 합과 오른쪽 길의 거리의 누적 합을 구해준다. 그리고 1번 지점부터 N번 지점까지, 각 지점에서 횡단보도를 건넜을 때 민주가 이동하는 거리의 최솟값을 구해준다. 이 때 이동 거리는 왼쪽에서 i번 지점까지 이동하는 거리 + i번 지점의 횡단보도의 길이 + (오른쪽에서 N번 지점까지 이동하는 거리 - 오른쪽에서 i번 지점까지 이동하는 거리)이다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e12

using namespace std;
int N;
LL Crossroad[MAX];
LL Left_Road[MAX];
LL Right_Road[MAX];
LL Answer_Pos, Answer_Len = INF;

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> Crossroad[i];
	}
	for (int i = 2; i <= N; i++) {
		int X;
		cin >> X;
		Left_Road[i] = Left_Road[i - 1] + X;
	}
	for (int i = 2; i <= N; i++) {
		int X;
		cin >> X;
		Right_Road[i] = Right_Road[i - 1] + X;
	}
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		LL Tmp = Left_Road[i] + Crossroad[i] + Right_Road[N] - Right_Road[i];
		if (Answer_Len > Tmp) {
			Answer_Len = Tmp;
			Answer_Pos = i;
		}
	}
}

void Find_Answer() {
	cout << Answer_Pos << " " << Answer_Len << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}