[백준 12841] 정보대 등산

i번째 길을 건널 때, i를 0부터 n까지 탐색하면서 최소가 되는 i를 찾고 마지막으로 계산함

최소를 찾을 때 i번째 횡단보도를 건너게 되면 전보다 a[i]만큼 더가지만 b[i]만큼 덜가므로

a[i] - b[i] 값을 한번 탐색할 때 마다 sum에 누적시키면서 시작했을 때보다 상대적으로 건너는게 이득인지 계산(음수일 경우 이득, cross는 제외하고 생각)

그리고 매번 cross값을 sum에 더하면 상대적인 비용을 알 수 있으므로 min값을 업데이트 하면서 index 저장

#include <iostream>
#define n_ 100005
using namespace std;
typedef unsigned long long ull;
int n;
int cross[n_];
int a[n_];
int b[n_];
 
int main(void) {
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> cross[i];
    }
 
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        cin >> b[i];
    }
    a[n] = b[n] = 0;
 
    int index = 0;
    long long sum = 0;
    long long min = cross[0];
    for (int i = 0; i < n - 1; i++) {
        int tmp = a[i] - b[i];
        sum += tmp;
        if (sum + cross[i + 1] < min) {
            index = i + 1;
            min = sum + cross[i + 1];
        }
    }
 
    sum = 0;
    for (int i = 0; i < n - 1; i++) {
        if (i < index) {
            sum += a[i];
        }
        else {
            sum += b[i];
        }
    }
 
    printf("%d %lld", index + 1, sum + cross[index]);
    return 0;
}