BOJ)12841 정보대 등산

문제: icpc.me/12841

왼쪽 1번 지점에서 오른쪽 n번 지점까지 가는 최단 거리를 구하는데 이 때 횡단보도는 한번 밖에 못 건넌다는 전제가 있다.

N개의 횡단보도를 건너는 케이스를 전부 확인을 해줘야 하는데 N이 10만이나 되기 때문에 

모든 케이스를 직접 더해줄 경우 TLE를 받을 수 있다.

하지만 Partial sum을 이용한다면 왼쪽 오른쪽길의 횡단보도 기준으로 위 아래는 쉽게 구할 수 있다.

주의 할 점은 10만개의 횡단보도에 거리가 10만 까지 들어올 수 있으므로 long long을 사용해줘야 한다.

#include <cstdio>
#include <algorithm>
#define INF 999999999987654321
using namespace std;
typedef long long ll;
ll n, x, r, ans;
ll a[100010], b[100010], c[100010];
int main() {
    scanf("%lld", &n);
    for (ll i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    for (ll i = 1; i < n; i++) {
        scanf("%lld", &x);
        b[i] = b[i - 1] + x;
    }
    for (ll i = 1; i < n; i++) {
        scanf("%lld", &x);
        c[i] = c[i - 1] + x;
    }
    r = INF;
    for (ll i = 0; i < n; i++) {
        ll y = a[i] + b[i] + c[n - 1] - c[i];
        if (y < r) {
            r = y;
            ans = i + 1;
        }
            
    }
    printf("%lld %lld", ans, r);
    return 0;
}