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/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

+ Recent posts

티스토리툴바