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

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

 

 

이 문제는 건너는 길목에 대해서 비용이 존재하며

왼쪽 길 횡단보도 오른쪽 길로 구성되어 있다. 이때 최소비용으로 시작점에서 정보대에 도착하는 비용을 출력하는 문제이다.

 

문제에서는 횡단보도를 한번만 건널 수 있다.

 

이때 지점의 개수는 10만개이기 때문에 단순히 완전탐색으로는 시간초과가 난다. 따라서 O(N)이나 O(N log N)의 풀이 방법을 찾아야 하는데 경우의 수를 구해보니 중복되는 것을 발견했고 이런 중복된것을 누적해서 합하면 점화식이 나온다고 생각하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N;
ll cross[100001];
ll leftbr[100001];
ll rightbr[100001];
ll answer = 1e18;
ll bridge;

void solve() {
    for(int i = 0; i < N; i++) {
        ll dist = leftbr[i] + cross[i] + rightbr[N-1] - rightbr[i];

        if(dist < answer) {
            answer = dist;
            bridge = i+1;
        }
    }
    cout << bridge << " " << answer;
}

void input() {
    cin >> N;

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

    for(int i = 1; i < N; i++) {
        cin >> leftbr[i];
        leftbr[i] += leftbr[i-1];
    }

    for(int i = 1; i < N; i++) {
        cin >> rightbr[i];
        rightbr[i] += rightbr[i-1];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

처음에는 그래프 관계가 주어진다고 생각해서 다익스트라 알고리즘을 사용하여 접근해야겠다고 생각했는데

그래프 연결관계를 어떻게 표현해야할지 생각이 안나서 일단 막 접근해서 풀어보았다.

중복되는 것을 발견하고 바로 누적합을 사용하여 식을 나타냈는데

꽤나 쉬웠던 문제였다.