티스토리 뷰

알고리즘 관련/BOJ

BOJ)12841 정보대 등산

JASON 자손9319 2017. 1. 5. 20:32

문제: icpc.me/12841


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


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13505 두수 XOR  (4) 2017.01.05
BOJ)12843 복수전공  (0) 2017.01.05
BOJ)12841 정보대 등산  (0) 2017.01.05
BOJ)1865 웜홀  (0) 2017.01.05
BOJ)11999 Milk Pails  (2) 2017.01.05
BOJ)10775 공항  (0) 2017.01.04
댓글
댓글쓰기 폼