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


LIS문제라는 것을 눈치채지 못한 저는 바보입니다.


LIS입니다..


전형적인 DP문제죠...


dp[n] : 인덱스 n까지의 최대 연결 수


라고 정의하면 됩니다.


이렇게 하면 N^2의 시간복잡도로 해결할 수 있습니다.


관련 문제..

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

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


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
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
#include <cstdio>
 
#define mp make_pair
#define MOD 1000000007
#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 pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int edge[501];
int dp[501];
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
 
        edge[a] = b;
    }
 
    int ret = 0;
 
    for (int i = 1; i <= 500; i++) {
        if (edge[i] == 0) continue;
 
        dp[i] = 1;
 
        for (int j = 1; j < i; j++) {
            if (edge[j] < edge[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
 
        ret = max(ret, dp[i]);
    }
    
    cout << n - ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1365] 꼬인 전깃줄  (0) 2017.09.16
[1890] 점프  (0) 2017.09.15
[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24

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


문제에서 인풋으로 GCD와 LCM을 줍니다.

우리는 그렇다면

어떤 수 a, b가 있다고 존재할 때

A = a / GCD

B = b / GCD

라고 한다면


LCM = GCD * A * B

라는 것을 알 수 있습니다.


여기서 가장 중요한 조건 ! A와 B는 서로소여야만 한다는 것입니다.

서로소라는 것은 두 수는 약수를 1만을 가진다는 것인데요.


이 조건을 만족하지 않으면 A와 B는 후보가 될 수 없습니다.

예륻 들어 GCD가 4라는 인풋이 들어왔는데 A가 2 B가 4라면

더 나눌 수 있는 수가 존재하므로 후보가 아니라는 말이죠.


그 외에는 어려운 부분은 없었습니다.

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
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
 
#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 pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int get_gcd(int a, int b) {
    return b ? get_gcd(b, a % b) : a;
}
 
int main() {
    int gcd, lcm;
    cin >> gcd >> lcm;
 
    int tmp = lcm / gcd;
 
    int left = 0, right = 0;
 
    for (int i = 1; i * i <= tmp; i++) {
        if (tmp % i == 0) {
            if (get_gcd(i, tmp / i) == 1) {
                left = i;
                right = tmp / i;
            }
        }
    }
 
    if (left > right) swap(left, right);
 
    cout << left * gcd << ' ' << right * gcd;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 수학' 카테고리의 다른 글

[13412] 서로소 쌍  (0) 2017.09.07
[1740] 거듭 제곱  (0) 2017.06.21

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


문제 이해를 잘못해서.. 해결하는데 엄청난 시간이 걸렸습니다.


이 문제는 (0, 0)에서 입력 받은 K이하의 노드를 거쳐서  (10000, 10000)으로 이동할 때 드는 연료의 최대값의 최솟값을 구하는 문제입니다.


(0, 0)을 A라고 가정하고 (10000, 10000)을 D라고 가정했을 때, A - B(임의의 노드)로 가는 연료가 1000이고 B - C(임의의 노드)로 가는 연료가 100이라면


A - B구간에서 1000만큼 필요했으므로 답은 1000이 나와야합니다.


이것을 모든 노드에 대해서 실행해보면 됩니다.


이분탐색을 이용해서 해당 비용만을 이용해서 (0, 0)에서 (10000, 10000) 목적지로 이동할 수 있는지를 계속해서 실행하면 됩니다.(bfs로)


코드입니다.

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 <queue>
#include <cmath>
#include <string.h>
 
#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 pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
vii pos;
bool visit[(int)1e3 + 2];
 
int d(pii a, pii b) {
    int x = b.first - a.first;
    int y = b.second - a.second;
 
    return (int)ceil(sqrt(x * x + y * y) / 10);
}
 
bool bfs(int max_cost, int n, int k) {
    memset(visit, 0, sizeof(visit));
 
    queue<pii> q;
    q.push(mp(0, 0)); // from, k
 
    while (!q.empty()) {
        int from = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (from == pos.size() - 1) {
            if (cnt <= k + 1) return 1;
            else return 0;
        }
 
        for (int i = 1; i < pos.size(); i++) {
            if (visit[i]) continue;
 
            if (d(pos[i], pos[from]) <= max_cost) {
                visit[i] = 1;
                q.push(mp(i, cnt + 1));
            }
        }
    }
    
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, k;
    cin >> n >> k;
 
    pos.push_back(mp(0, 0));
 
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
 
        pos.push_back(mp(a, b));
    }
 
    pos.push_back(mp(1e4, 1e4));
 
    int left = 1, right = d(mp(0, 0), mp(1e4, 1e4));
 
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (bfs(mid, n, k)) right = mid - 1;
        else left = mid + 1;
    }
 
    cout << left;
 
    return 0;
}
cs


저작자표시

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

[12842] 튀김 소보루  (0) 2017.08.23
[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/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

+ Recent posts

티스토리툴바