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


이분 탐색할 것은.. 각 나무당 몇 미터를 자를 것이냐 ? 입니다.

이 문제는 꽤 쉬우므로..


해당 나무의 높이 보다 더 높이 자를 경우 -의 나무는 없으므로 0을 총 길이에 더하는 점만 조심하면

평이한 것 같습니다..


설명이 부족하다고 느끼실 땐 댓글 달아주세요!! 상세하게 설명해드릴 자신 있습니다.!!!


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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define MAX_SIZE 1000000
 
int height[MAX_SIZE];
 
int main()
{
    int n, m;
 
    scanf("%d %d", &n, &m);
 
    int max_height = 0;
 
    for(int i = 0; i < n; i++) scanf("%d", height + i);
    for(int i = 0; i < n; i++) max_height = height[i] > max_height ? height[i] : max_height;
 
    int left = 1, right = max_height;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        long long sum = 0;
 
        for(int i = 0; i < n; i++) sum += height[i] - mid > 0 ? height[i] - mid : 0;
 
        if(sum < m) right = mid - 1;
        else left = mid + 1;
    }
 
    printf("%d\n", right);
 
    return 0;
}
 
cs


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

[2585] 경비행기  (0) 2017.08.30
[12842] 튀김 소보루  (0) 2017.08.23
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19

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


이 문제는 각 나라에 배정할 예산을 탐색하면 됩니다.

조심할 점은 내가 탐색할 예산액보다 요구하는 양이 적은 지방은 다 주지말고 그냥 전체 예산액에서 빼줘야한다는 점과

더 많은 지방에는 예산액만큼만 줘야한다는 점입니다. 이 두개만 조심하면 쉬운 문제인 것 같습니다.


아 추가로.. 만약 각 지방이 요구하는 금액이 국가 에산보다 적을 시에는 그냥 요구하는 금액만큼 주면되므로 그 중 최대값을 출력하면됩니다.

아래의 코드입니다.

1
2
3
4
5
6
7
    for(int i = 0; i < n; i++)
    {
        tmp -= money[i];
        max_money = money[i] > max_money ? money[i] : max_money;
    }
 
    if(tmp >= 0) return printf("%d\n", max_money), 0;
cs

 전체 코드입니다.

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 <cstdio>
#include <algorithm>
#include <iostream>
 
#define MAX_SIZE 10000
#define INF 1e9
 
using namespace std;
 
int money[MAX_SIZE];
 
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &money[i]);
 
    int total;
    scanf("%d", &total);
 
    int tmp = total;
    int max_money = 0;
 
    for(int i = 0; i < n; i++)
    {
        tmp -= money[i];
        max_money = money[i] > max_money ? money[i] : max_money;
    }
 
    if(tmp >= 0) return printf("%d\n", max_money), 0;
 
    int left = total / n, right = max_money;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        tmp = total;
 
        for(int i = 0; i < n; i++)
        {
            if(mid >= money[i]) tmp -= money[i];
            else tmp -= mid;
        }
 
        if(tmp >= 0) left = mid + 1;
        else right = mid - 1;
    }
 
    printf("%d\n", right);
 
    return 0;
}
 
cs


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

[12842] 튀김 소보루  (0) 2017.08.23
[2805] 나무 자르기  (3) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19
[2110] 공유기 설치  (0) 2017.04.19

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

이분탐색 문제의 해결방법은 계속 강조하지만 무엇을 탐색할 것인가?를 고민하면됩니다.
(물론 이 문제가 이분탐색인가?? 라는 것을 알기가 힘들긴 합니다..)


이 문제는 블루레이의 크기를 최소로 만들면 됩니다..


굳이 조심해야할 점은 마지막에 레쓴이 남았을 때 CD를 한장 더만들어줘야한다는 점..??


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 <cstdio>
#include <algorithm>
#include <iostream>
 
#define MAX_SIZE 100000
#define INF 1e9
 
using namespace std;
 
int lesson[MAX_SIZE];
 
int main()
{
    int n, c;
    scanf("%d %d", &n, &c);
 
    int max_lesson = 0;
 
    for(int i = 0; i < n; i++)
    {
        scanf("%d", lesson + i);
        max_lesson = lesson[i] > max_lesson ? lesson[i] : max_lesson;
    }
 
    int left = max_lesson, right = INF / c;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        int sum = 0;
        int bluelay = 0;
 
        for(int i = 0; i < n; i++)
        {
            if(sum + lesson[i] > mid)
            {
                sum = 0;
                bluelay++;
            }
            sum += lesson[i];
        }
 
        if(sum != 0) bluelay++;
 
        if(bluelay <= c) right = mid - 1;
        else left = mid + 1;
    }
 
    printf("%d\n", left);
 
    return 0;
}
 
cs


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

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19
[2110] 공유기 설치  (0) 2017.04.19
[1300] K번째 수  (0) 2017.04.06

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


이분 탐색을 재귀로 구현해보았습니다!

여기서 중요한 것은 mid와 left right를 롱롱형으로 처리한다는 점입니다.

right 초기값을 signed int의 최대값으로 설정했기 때문에 1 + right를 할 경우에

int범위를 벗어나게 됩니다. 그러므로 롱롱형으로 처리를 했습니다.


이 문제도 마찬가지로 무엇을 이분탐색으로 탐색할 것인가??에 대해서 고민하면 쉽게 풀 수 있습니다.

여기서 탐색할 것은 랜선의 길이입니다. 각 랜선에서 몇미터짜리의 랜선으로 자를 것인가!
처음에 최대값부터 시작해서... 이분탐색을 합니다!

임의의 값으로 랜선을 잘랐을 때 랜선의 수가 요구하는 개수보다 많아지면 더 길게!

반대의 경우는 짧게 탐색을 합니다.

조심해야할 점은 문제에서 최대 길이를 요구했으므로

어떤 길이로 잘랐을때 랜선의 개수 N을 만족하더라도 더 긴 길이의 랜선으로 만들어보아야합니다.

예를들어 200으로 잘랐는데도 랜선 N개를 만족할 수도 있고 201도 만족한다면 답은 201이 되어야한다는 말입니다.


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
#include <cstdio>
#define MAX_SIZE 10000
#define INF 0x7fffffff
#define ll long long
int data[MAX_SIZE];
int k, n;
int ret;
 
int binary_search(int key, ll left, ll right)
{
    if(left > right) return -1;
 
    ll mid = (left + right) / 2;
 
    int cnt = 0;
    for(int i = 0; i < k; i++) cnt += data[i] / mid;
 
 
    if(cnt >= key)
    {
        ret = mid > ret ? mid : ret;
        return binary_search(key, mid + 1, right);
    }
    else if(cnt < key) return binary_search(key, left, mid - 1);
 
}
 
int main()
{
 
    scanf("%d %d", &k, &n);
 
    for(int i = 0; i < k; i++) scanf("%d", data + i);
 
    binary_search(n, 1, INF);
 
    printf("%d", ret);
 
    return 0;
}
 
cs


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

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[2110] 공유기 설치  (0) 2017.04.19
[1300] K번째 수  (0) 2017.04.06

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

이 문제는 저는 개인적으로 꽤 어려웠는데요....

이분 탐색으로 풀 수 있는 문제입니다..

파라메트릭 서치(?)라고.. K번째 수와 마찬가지로 이분 탐색의 응용인 문제인데

집의 수와 공유기의 수 그리고 집의 좌표를 줍니다.


최대한 넓게 넓게 설치해서 인풋으로 요구하는 공유기의 수를 만들어야 하는데..

여기서 어떻게 이분탐색을 하느냐에 대해서 엄청나게 고민했습니다.


결론부터 말하자면! 우리는 거리를 가지고 이분탐색을 해야합니다.


예를 들어 거리를 10으로 첫 시작을 했다면 10간격으로 설치를 해보고 공유기가 더 많이 필요하면 간격을 늘리고

공유기가 덜 설치되었으면 거리를 줄이는 방식으로 이분탐색을 진행하면 됩니다.


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
#include <cstdio>
#include <algorithm>
#define MAX_SIZE 200000
 
int pos[MAX_SIZE];
 
int main()
{
    int n, c;
    scanf("%d %d", &n, &c);
 
    for(int i = 0; i < n; i++) scanf("%d", pos + i);
 
    std::sort(pos, pos + n);
 
    int left = 1, right = pos[n - 1] - pos[0];
    int ret;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        int cnt = 1;
        int start = pos[0];
 
        for(int i = 1; i < n; i++)
        {
            if(pos[i] - start >= mid)
            {
                cnt++;
                start = pos[i];
            }
        }
 
        if(cnt >= c)
        {
            ret = mid;
            left = mid + 1;
        }
        else right = mid - 1;
 
    }
 
    printf("%d\n", ret);
 
 
    return 0;
}
 
cs


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

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19
[1300] K번째 수  (0) 2017.04.06

K번째 수 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB107631821936.139%

문제

세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.)

그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다.

세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 정렬해서 k번째 원소를 구하려고 한다.

N이 주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다.

출력

k번째 원소를 출력한다.

예제 입력 

3
7

예제 출력 

6

힌트
















　　　　　　　　　　　　　　　　　　　　　

너무 어려워서... 블로그 돌아다니면서 공부했습니다...

사실 아직도 정확히 이해가 안가네요...


의문점 1.. return값이 왜 left일까요...

cnt >= k 같을 경우 mid를 임시로 저장해서 끝까지 탐색한 다음 임시로 저장한 값을 출력하는 건 이해가 가는데

left가 결국 결과값이 되는 부분은 이해가 안가네요.


의문점 2.. 어째서 right에 n^2이 아닌 k를 넣는건지 잘모르겠습니다..

음.. 당연히?? k가 내가 찾는 수 보다 크기 때문에 불필요한 탐색을 줄이기 위함일까요????


세번째 의문... 이 방법을 어떻게 사람들은 생각한걸까요.. 천재일까요 T__T..머리가 너무 부럽네요..

처음에 if(cnt == k) return mid;가 왜 아닌가에 대해서 고민했는데...

i*j로 표현할 수 없는 수가 있을 수 있다고 하는데... 이것 또한 어떻게 ..생각하는 걸까요..후..



아참... 이분탐색에서 for문을 돌리는 이유는 mid값보다 작거나 같은 수를 체크하기 위함입니다.

mid / i와 n의 크기를 비교해서 작은 값을 쓰는 이유는 예를들어 n이 4라면 테이블이 아래처럼 만들어질 것입니다.


 1  2  3  4

 2  4  6  8

 3  6  9 12

 4  8 12 16


mid가 만약 6이라면 i == 1일 때 n = 4와 6 / 1 을 비교하게 됩니다.

하지만 1의 배수 중에 가장 큰 수는 4이므로 6개가 될수 없습니다.

그렇기 때문에 1의 배수 중에서 6보다 작은 수는 4개가 되겠죠.


마찬가지로 i == 2일 때 2의 배수에서도 6보다 작거나 같은 수를 찾습니다.

6/2를 하면 2, 4, 6이 포함되는 3이되겠죠.. 그렇게해서 3개


i == 3일 땐 같은 방법으로 3, 6을 포함한 2개

i == 4일 때는 4를 포함한 1개입니다.


총 카운트는 4 + 3 + 2 + 1 = 10 입니다.


이렇게 함으로써 mid보다 작은 수의 갯수를 셀 수 있습니다.



완벽히 이해는 못했지만 코드는 올리겠습니다.


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
#include <stdio.h>
#include <algorithm>
 
int n, k;
 
int binary_search(int left, int right)
{
    if(left > right) return left;
 
    int mid = (left + right) / 2;
    int cnt = 0;
 
    for(int i = 1; i <= n; i++) cnt += n > mid / i ? mid / i : n;
 
    if(cnt < k) return binary_search(mid + 1, right);
    else return binary_search(left, mid - 1);
}
 
int main()
{
    scanf("%d %d", &n, &k);
 
    printf("%d", binary_search(1, k));
 
    return 0;
}
cs


백준에 똑같이 질문을 올렸더니 dotorya님께서 친절히 답해주셨습니다.

그림자라도 쫓을 수 있게 열심히 공부해야겠습니다.


dotorya 

1. return값이 Left가 된다는 부분 자체는 사람들마다 구현이 다르기 떄문에.. 굳이 큰 의미를 둘 이유는 없다고 생각합니다.

저도 다른 분들의 이분탐색 코드를 읽을 때는 시간이 좀 걸리는 편입니다.

다만, "cnt >= k인 가장 작은 숫자"를 탐색하고 있다는 사실만 잘 염두에 두고 코딩하신다면 문제 없을 거라고 생각합니다.


2. 생각하신 것이 맞는 것 같습니다.

추가로 N*N을 기준으로 탐색하면 long long 변수를 써야하는 귀찮음도 있을 것 같습니다.

* 여기에 더해서 드리는 말씀인데, 위 코드에서 cnt 변수에 overflow가 발생할 가능성이 없을지는 한번 확인해보시는게 좋을 것 같습니다.

아마 발생하지 않을 것 같긴 한데, 명확하게 증명해 보는게 좋겠죠..


3. 이런 방법을 처음 볼 때는 아마 누구라도 생각하기 어려울 것 같습니다.

이 문제처럼 답을 정해놓고 그 답이 가능한지 이진탐색하는 종류의 문제들을 Parametric Search라고 합니다.

사람들이 이 문제를 잘 생각하는 건, 어떻게 보면 이런 종류의 문제가 수십개씩 있었기 때문이라고도 생각되네요.

다음에 이런 문제가 나왔을 때 이 아이디어를 떠올릴 수만 있으면, 그것만으로도 잘 배우신 것이 아닐까요?

결국 그런 지식들과 응용할 수 있는 능력들이 모여서 실력이 쌓이는 거라고 생각합니다.


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

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19
[2110] 공유기 설치  (0) 2017.04.19

+ Recent posts

티스토리툴바