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


이 문제는 MST로 해결할 수 있습니다.

MST라고 생각한 이유

1. 모든 집은 전부 연결되어야 한다.

2. 필요 없는 다리는 제거한다.(유지 비용이 작은 다리만 남겨둔다.)


이 두 가지 조건을 보고 MST라고 생각했습니다.

그렇다면 한 마을을 두 마을로 어떻게 나눌까요?


진짜 간단합니다.

두 마을로 나눴을 때 한쪽 마을에 집이 한 채 이상이라면 두 마을로 나눠진 것입니다.


즉, 크루스칼을 이용하여 n - 2개의 다리만 연결하면 됩니다.

왜 n - 1이 아닌 n - 2인지 설명해드리겠습니다.


우선 마을이 하나라고 생각하고 MST를 이용해 모든 집을 연결하겠지요?

그리고 두 마을로 나눠야하는데

제가 생각했을 때 어차피 최소 비용을 유지하려면 가장 유지비가 큰 다리를 제거하면 된다는 것입니다.

그래서 n - 1개를 연결하고 그 다리 중에 가장 큰 비용의 다리 하나를 제거하면 된다는 뜻이 됩니다.


근데 크루스칼은 어차피 최소 비용을 가진 것 부터 처리하므로 애초에 마지막 다리를 설치하지도 않은 채 n - 2개의 다리만

연결한다면 문제를 해결할 수 있습니다.


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
#include <queue>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<int, int> vii;
typedef vector<ll, ll> vll;
 
int parent[MAX_SIZE];
 
int find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}
 
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
 
    if (x != y) {
        parent[x] = y;
        
        return 1;
    }
 
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) parent[i] = i;
 
    priority_queue < pair<int, pii> > pq;
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
 
        pq.push(mp(-c, mp(a, b)));
    }
 
    int sum = 0;
    int cnt = 0;
 
    while (!pq.empty() && cnt < n - 2) {
        int cost = -pq.top().first;
        int a = pq.top().second.first;
        int b = pq.top().second.second;
        pq.pop();
 
        if (!merge(a, b)) continue;
        
        cnt++;
        sum += cost;
    }
 
    cout << sum;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 최소 스패닝 트리(MST)' 카테고리의 다른 글

[13418] 학교 탐방하기  (0) 2017.07.11

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


세그먼트 트리 lazy전파 유형입니다.

N만 작으면 비트마스크로 해결할 수 있을 것이라 생각했는데..

N도 너무 크고.. 흠.. 잘생각이 나지않았습니다.

스위치의 상태를 체크하려면 항상 그 범위만큼의 시간이 필요합니다.


하지만 lazy를 사용하면 해당 범위의 아래 부분은 나중에 업데이트를 하면 됩니다.

그리고 해당 범위의 노드에서 스위치 개수를 뒤집는 방법은

tree[node] = end - start + 1 - tree[node];

이용하면 됩니다.


범위의 개수에서 현재 on개수를 빼면 off개수가 나오기 때문이죠!


아래는 코드입니다.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <cmath>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<int, int> vii;
typedef vector<ll, ll> vll;
 
 
void update_lazy(vi &tree, vi &lazy, int node, int start, int end) {
    if (lazy[node]) {
        tree[node] = end - start + 1 - tree[node];
 
        if (start != end) {
            lazy[node * 2] = !lazy[node * 2];
            lazy[node * 2 + 1] = !lazy[node * 2 + 1];
        }
 
        lazy[node] = 0;
    }
}
 
int update_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) {
        return tree[node];
    }
    else if (left <= start && end <= right) {
        tree[node] = end - start + 1 - tree[node];
 
        if (start != end) {
            lazy[node * 2] = !lazy[node * 2];
            lazy[node * 2 + 1] = !lazy[node * 2 + 1];
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right) + update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int sum_query(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) {
        return 0;
    }
    else if (left <= start && end <= right) {
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return sum_query(tree, lazy, node * 2, start, mid, left, right) + sum_query(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    int tree_size = ceil(log2(n)) + 1;
    vi st(1 << tree_size);
    vi lazy(1 << tree_size);
 
    for (int i = 0, cmd, a, b; i < m; i++) {
        cin >> cmd >> a >> b;
 
        if (cmd) {
            cout << sum_query(st, lazy, 1, 1, n, a, b) << '\n';
        }
        else {
            update_range(st, lazy, 1, 1, n, a, b);
        }
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 세그먼트트리, 펜윅트리' 카테고리의 다른 글

[12844] XOR  (0) 2017.08.26
[2517] 달리기  (0) 2017.08.16
[10999] 구간 합 구하기 2  (0) 2017.08.15
[2042] 구간 합 구하기  (0) 2017.08.15

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


헉헉..

엄청 어렵네요!!..


pre, in, post 각각의 순회는 이해했지만,

완벽히 이해한 것은 아니였나봅니다.


이 문제는

in과 post를 이용하여 pre를 유추하는 문제입니다.


post와 in의 특징을 제대로 이해하고 있다면

O(N)의 시간으로 해결할 수 있습니다.


우선 post에 특징에 대해서 말씀드리겠습니다.


post는 Left - Right - Root 순으로 순회를 합니다.

그렇다면 우리가 받는 post input에서 가장 끝이 트리의 root라는 것을 알 수 있습니다.


예제를 예로 들면 1 3 2 로 들어오니 2가 root라는 것을 알 수 있죠.


두번째로 in의 특징입니다.

in은 Left - Root - Right 순으로 순회를 합니다.

여기서 중요한 점!은 바로 in의 input을 그대로 받는 것이 아닌 그의 위치를 저장하는 것입니다.


예제를 예로 들면

1 2 3 이라는 input이 들어오니, pos[1] = 0, pos[2] = 1, pos[3] = 2

이런 식으로 위치를 저장합니다.

그 이유는


in을 사용해서 우리는 left, right 서브트리와 root로 구분을 지을 수 있기 때문입니다.


post를 이용하여 root를 찾았고, root가 무엇인지 안다면 in에서 그 root를 기준으로 left와 right 서브트리로 나눌 수 있습니다.


이러한 과정을 분할하면서 계속 반복한다면 원래의 트리 모양을 유추할 수 있겠지요.


pre는 Root - Left - Right 이므로 위의 특징들을 이용하여 root를 찾아낸 후 출력하고 in의 root를 기준으로

left서브트리의 노드 수와 right 서브트리의 노드 수를 체크하여 post트리에 적용한 후 그 노드 수를 기준으로 나눠주면 됩니다.



코드입니다.

pos배열을 선언할 때 배열의 개수가 MAX_SIZE + 1인 이유는 input이 1~N까지 들어오기 때문입니다.(이것 떄문에 엄청 틀렸습니다.)


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int post[MAX_SIZE];
int pos[MAX_SIZE + 1];
 
void order(int is, int ie, int ps, int pe) {
    if (is > ie || ps > pe) return;
 
    int root = post[pe];
    cout << root << ' ';
 
    order(is, pos[root] - 1, ps, ps + pos[root] - is - 1);
    order(pos[root] + 1, ie, ps + pos[root] - is, pe - 1);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0, in; i < n; i++) {
        cin >> in;
        pos[in] = i;
    }
 
    for (int i = 0; i < n; i++) {
        cin >> post[i];
    }
 
    order(0, n - 1, 0, n - 1);
 
    return 0;
}
 
cs


저작자표시

'CS기본지식 > 자료구조' 카테고리의 다른 글

[C언어] 원형 큐(라운드 큐)  (0) 2017.09.07
[C언어] 우선순위 큐(Priority Queue)  (3) 2017.09.07
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13
이중 연결 리스트  (0) 2017.04.22

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


lazy를 이용한 세그먼트 트리로 문제를 해결했습니다.-


XOR은 같은 값을 여러번하는 것은 의미없습니다.

한번하거나 안하거나와 같습니다.

홀수번 = 한번

짝수번 = 아예 안한 것


과 같기 떄문에 이 점을 이용해서 문제를 해결했습니다.


나머지 부분은 부분합 구하는 세그먼트 트리와 유사합니다.


코드입니다.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[500000];
 
int init(vi &tree, int node, int start, int end) {
    if (start == end) return tree[node] = arr[start];
    
    int mid = (start + end) / 2;
    return tree[node] = init(tree, node * 2, start, mid) ^ init(tree, node * 2 + 1, mid + 1, end);
}
 
void update_lazy(vi &tree, vi &lazy, int node, int start, int end) { 
    if (lazy[node] != 0) {
        tree[node] ^= lazy[node] * ((end - start + 1) % 2);
 
        if (start != end) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
 
int update_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right, int value) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return tree[node];
    else if (left <= start && end <= right) {
        tree[node] ^= value * ((end - start + 1) % 2);
 
        if (start != end) {
            lazy[node * 2] ^= value;
            lazy[node * 2 + 1] ^= value;
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right, value) ^ update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right, value);
}
 
int xor_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return 0;
    else if (left <= start && end <= right) return tree[node];
    
    int mid = (start + end) / 2;
    return xor_range(tree, lazy, 2 * node, start, mid, left, right) ^ xor_range(tree, lazy, 2 * node + 1, mid + 1, end, left, right);
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int height = ceil(log2(n));
    vi tree(1 << (int)(height + 1));
    vi lazy(1 << (int)(height  + 1));
 
    init(tree, 1, 0, n - 1);
 
    int m; 
    cin >> m;
    
    for (int i = 0; i < m; i++) {
        int cmd;
        int a, b, c;
        cin >> cmd;
 
        if (cmd == 1) {
            cin >> a >> b >> c;
            if (a > b) swap(a, b);
            update_range(tree, lazy, 1, 0, n - 1, a, b, c);
        }
        else {
            cin >> a >> b;
            if (a > b) swap(a, b);
            cout << xor_range(tree, lazy, 1, 0, n - 1, a, b)<< '\n';    
        }
    }
 
 
    return 0;
}
cs


저작자표시

'알고리즘 > 세그먼트트리, 펜윅트리' 카테고리의 다른 글

[1395] 스위치  (0) 2017.08.30
[2517] 달리기  (0) 2017.08.16
[10999] 구간 합 구하기 2  (0) 2017.08.15
[2042] 구간 합 구하기  (0) 2017.08.15

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


간단한 문제입니다.

레벨이 변하지 않으므로, 최대값의 레벨을 가진 카드의 양방향으로 더해나가면 해결되는 문제입니다.


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
int n;
int arr[(int)1e3];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    int M = 0;
    int pos;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
 
        if (arr[i] > M) {
            M = arr[i];
            pos = i;
        }
    }
 
    int ret = 0;
 
    for (int i = pos - 1; i >= 0; i--) {
        ret += M + arr[i];
    }
 
    for (int i = pos + 1; i < n; i++) {
        ret += M + arr[i];
    }
 
    cout << ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[3190] 뱀  (4) 2018.01.10
[2140] 지뢰찾기  (0) 2017.12.27
[12841] 정보대 등산  (0) 2017.08.23
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30

어휴.. 엄청 어렵네요..


이분 매칭일 것이라고 생각은 했는데


어떻게 적용해야할까?가 문제였습니다.


중복되는 강의를 제외하고 어떻게 연결을 하지.. 라는 엄청난 고민...


나는 바보였다!!!!!!!!!!!!...


중복된 과목끼리 선을 만들어서 N개의 과목 - 중복된 과목 을 하면 정답이 나오는 것을...


역발상인거 같아요!!


무언가 풀다가 막히면 항상 거꾸로 역발상하는 방법도 생각해보는 것도 좋을 것 같습니다.


중복을 피하는 것이 아닌 중복을 찾는다...

어려웠습니다...

후!


그걸 제외하고는 다른 이분매칭과 다르지 않습니다.

이분 매칭을 리마인드하기 좋은 문제였습니다..

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int n, m;
 
vi edge[2001];
bool visit[2001];
 
int A[2001];
int B[2001];
 
vi vi_left;
 
bool f(int idx) {
    visit[idx] = 1;
 
    for (int i = 0; i < edge[idx].size(); i++) {
        int to = edge[idx][i];
 
        if (!B[to] || (!visit[B[to]] && f(B[to]))) {
            B[to] = idx;
            A[idx] = to;
 
            return 1;
        }
    }
 
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        int a;
        char major;
 
        cin >> a >> major;
        
        if (major == 'c') {
            vi_left.push_back(a);
        }
    }
 
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
 
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
 
    int ret = n;
 
    for (int i = 0; i < vi_left.size(); i++) {
        memset(visit, 0, sizeof(visit));
 
        ret -= f(vi_left[i]);
    }
 
    cout << ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 네트워크 플로우' 카테고리의 다른 글

[1671] 상어의 저녁식사  (0) 2017.07.02
[1017] 소수 쌍  (0) 2017.06.27
[6086] 최대유량  (1) 2017.06.03

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


흠.. 딱 보자마자!

이분탐색이 떠올랐습니다.


왜냐하면.. 그만큼 빵을 먹는데 걸린 시간을 알아야 한다고 생각했기 때문입니다.


그래서 이분 탐색으로 빵을 먹는데 걸린 가장 근접한 시간을 구합니다.


그거까진 어렵지 않았는데..

문제는

누가 먹었는지 유추하는 부분이었습니다.


문제의 예제를 보면

3명이 25개를 먹는데 걸리는 시간은 15초가 걸립니다.


그 이유는


1번은 1초

2번은 3초

3번은 5초라고 입력이 들어왔는데


15초면 1번은 16개를 먹을 수 있고

2번은 6개

3번은 4개


이렇게해서 총 26개를 먹을 수 있습니다.


1000-975는 25인데 26개를 먹으면 안되지 않나요??

네 맞습니당!

25개만 먹어야합니다.


그러면 14초를 한번 예로 들어볼까요

1번은 15개

2번은 5개

3번은 3개 

이렇게 총 23개를 먹을 수 있죠

그렇기 때문에 가장 근접한 시간은 15초입니다.


여기서 저는 나머지를 이용하여 해당 시간에 가장 근접한 집합을 구했습니다.

15초일 때 가장 근접한 집합은 1,2,3번 셋다 가능합니다.

3명 다 먹는 시간이 나누어 떨어지기 때문입니다.


그래서 15초에 총 먹은 수 26개에서 우리가 25개를 빼고

그 집합의 끝에서 찾아보면 답을 얻을 수 있습니다.


집합의 크기는 3(1, 2, 3) 그리고 15초에 먹은 수 26 - 우리가 구해야하는 수 25

1이 나오죠!


집합의 오른쪽부터 1이동한 정답은 2가 됩니다!


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <string>
#include <vector>
#include <queue>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int t[(int)1e5];
 
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, tmp;
    cin >> n >> tmp;
    n -= tmp;
 
    int k;
    cin >> k;
 
    for (int i = 0; i < k; i++) {
        cin >> t[i];
    }
 
    int left = 0, right = 1e5;
 
    while (left <= right) {
        int mid = (left + right) / 2;
        int eat = 0;
 
        for (int i = 0; i < k; i++) {
            eat += mid / t[i] + 1;
        }
 
        if (eat >= n) right = mid - 1;
        else left = mid + 1;
    }
 
    //left시간
    vi ret;
    int sum = 0;
    int v = 1e3; // 가장 근접한 나머지 값
 
    for (int i = 0; i < k; i++) {
        int rest = left % t[i];
        sum += left / t[i] + 1;
 
        if (rest < v) {
            ret.clear();
            ret.push_back(i + 1);
            v = rest;
        }
        else if (rest == v) ret.push_back(i + 1);
    }
 
    sum -= n; // left초 동안 먹은 빵의 양에서 우리가 구하고자 하는 빵의 양을 뺌
 
    cout << ret[ret.size() - 1 - sum]; // 백터의 끝에서 sum을 빼주면 답을 얻을 수 있음.
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 이분 탐색' 카테고리의 다른 글

[2585] 경비행기  (0) 2017.08.30
[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19

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


단순 구현? 일 것 같습니다.


횡단보도를 한 번만 할 수 있다?


즉. 왼쪽길로 쭉 가다가 횡단보도 한번 건너서 오른쪽 길로 쭉 갈 수 밖에 없습니다.

여기서 두가지 예외는 왼쪽 길로 아예 안가고 횡단 보도를 바로 건너서 오른쪽 길로 쭉 가는 방법과

왼쪽 길로 쭉 가서 횡단 보도를 건너서 정보대에 도착하는 방법이 있는데

사실 예외라고 하기엔.. 예외처리를 안해줘도 되기 때문에....ㅎㅎ...



그림으로 표현하면 이렇습니다!

빨간색길과 검은색길 초록색 길!


다 같은 말이죠


그렇다면 i번째에서 횡단보도를 건너는 거리의 식은


거리i = i번째 까지의 왼쪽 길 연속 합 + 횡단 보도 i의 거리 + 1부터 정보대까지의 오른쪽 거리 - 1부터 i까지의 거리


입니다.!


코드는 아래와 같습니다.


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <string>
#include <vector>
#include <queue>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int cross[MAX_SIZE + 1];
ll edge[MAX_SIZE + 1][2];
 
int main() {
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) cin >> cross[i];
 
    for (int i = 0; i < 2; i++) {
        for (int j = 2; j <= n; j++) {
            cin >> edge[j][i];
            edge[j][i] += edge[j - 1][i];
        }
    }
 
    ll ret = 1e16;
    int idx = 0;
 
    for (int i = 1; i <= n; i++) {
        ll tmp = edge[i][0] + cross[i] + edge[n][1] - edge[i][1];
 
        if (tmp < ret) {
            ret = tmp;
            idx = i;
        }
    }
 
    cout << idx << ' ' << ret;
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[2140] 지뢰찾기  (0) 2017.12.27
[12845] 모두의 마블  (0) 2017.08.26
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30
[14488] 준오는 급식충이야!  (0) 2017.07.29

+ Recent posts

티스토리툴바