정보대 등산 (백준 12841)

안녕하세요. 오늘은 등산을 할 거예요.

문제

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

아이디어

i번째 횡단보도를 사용하면 1번부터 i번까지는 왼쪽도로, i번부터 N번까지는 오른쪽 도로를 사용하게 됩니다. 누적합을 사용하면 됩니다.

소스코드

#include <iostream>
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    long long N, i, cross[101010] = { 0 }, Left[101010] = { 0 }, Right[101010] = { 0 }, leftsum[101010] = { 0 }, rightsum[101010] = { 0 };

    cin >> N;
    for (i = 1; i <= N; i++) cin >> cross[i];
    for (i = 1; i <= N - 1; i++) cin >> Left[i];
    for (i = 1; i <= N - 1; i++) cin >> Right[i];

    for (i = 1; i <= N - 1; i++) leftsum[i] = leftsum[i - 1] + Left[i];
    for (i = N - 1; i >= 1; i--) rightsum[i] = rightsum[i + 1] + Right[i];

    long long mn = 2e18, p = 0;
    for (i = 1; i <= N; i++)
    {
        long long sum = cross[i] + leftsum[i - 1] + rightsum[i];
        if (mn > sum)
        {
            mn = sum;
            p = i;
        }
    }
    cout << p << ' ' << mn;
}

감사합니다.