이분탐색을 시작하는 분들도 쉽게 풀만한 문제라고 생각된 문제중 하나였다. 

배열 A[i][j] = i*j라는 특성을 사용해서 결국 행*열의 곱이라는 말이다. 굳이 일차원배열로 늘어놓고

정렬을 안해도되고, 하게된다면 시간초과의 난관을 겪을 것이다. 

예를들어보자 n이 5일때 1*1, 1*2, 1*3, 1*4, 1*5, 2*1, ... 이다.

6이라는 수를 가정하고 몇번째 수인지 따저본다. 1행에서 6보다 작은수는 6/1 즉 6개 

2행에서는  6/ 2 = 3개 이런식이다. 실제로 2,1   2,2    2,3 이렇게 3개인것이다. 

따라서 그냥 lft를 1로 설정하고 k번째 수가 절대 k보다 클리는 없으므로 k로 상한을 잡고 

이분탐색을 돌리면 되는것이다. 

실제로 풀어보면 이분탐색에 대한 자신감이 팍팍 솟는 문제!


1300번: K번째 수
1300번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 K번째 수 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 2495 772 567 35.130% 문제 세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.) 그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다. 세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 정렬해서 k번째 원소를 구하려고 한
www.acmicpc.net

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

<Code>

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
// pda_pro12
#include<algorithm>
#include<iostream>
#define N_ 100000
using namespace std; 
typedef long long ll; 
 
int a, b, ans; ll lft, rgt; 
 
int main() {
    cin >> a >> b;
 
    lft = 1;  rgt = b; 
 
    while (lft <= rgt) {
        int mid = (lft + rgt) >> 1;   // 가정된 K번째 
        ll Sum = 0; 
        for (int i = 1; i <= a; i++)    // 행마다 mid보다 작은수의 갯수를 측정
            Sum += min(a, mid / i); 
        if (Sum >= b)
            rgt = mid - 1, ans = mid;
        else
            lft = mid + 1; 
    }
    cout << ans; 
    return 0; 
}


저작자표시

'PS) BOJ > Binary Search' 카테고리의 다른 글

[C++]수열 걷기[백준 4929]  (0) 2018.08.21
[C++] 랜선 자르기 [BOJ 1654]  (0) 2018.08.16
[C++] 게임 [백준 1072]  (0) 2018.08.16
[C++]입국심사[백준 3079]  (0) 2018.08.15

아이디어 도출해놓고 자료형 실수와 오버플로우를 예측하지 못해 30분동안 삽질한...문제였다...

먼저 향상된 게임실력으로 더이상 지지않는다는 전재가 있으므로 

확률 z = (y(이긴 게임 수)/x(총게임수))*100 이 바뀌기 위해 추가로 진행해야하는 최소의 게임수를 

구하는 문제이다. 최소의 게임수라는 말은 없지만 확률이 변하는 순간의 게임수이므로 최소의 게임

수를 구하면 된다. 

문제 풀이 순서

1. 하한을 0게임으로 잡고 상한을 1000000001로 잡았다(상한 잘못 잡아서 고생했다...)

2. 이분탐색으로 (하한+상한)/2만큼 추가게임을 진행하였을때의 확률을 계산하여 확률이 변하였는지
   확인해본다. 

3. 확률이 변했다면 상한값을 줄이고, 변하지 않았다면 하한값을 중간값+1방식으로 늘려간다. 

4. 이렇게 left <= right를 만족할때까지 진행되므로 결국 하한에 수렴하도록 mid를 설정하고 검사한
     다.

5. 빠저나왔을때의 left값은 확률이 변하는 순간의 하한이다.

자료형과 범위에서 실수로 고생한걸 보면서 한참 멀었구나를 느꼇다...

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

<Code>


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
// pda_pro12
#include<algorithm>
#include<iostream>
 
#define INT 0x7fff0000
#define MAX_ 1000000001
 
using namespace std;
 
typedef long long ll;
ll x, y, z; ll lft, rgt;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    while (cin >> x >> y) {
        z = y * 100 / x;
        lft = 0;  rgt = MAX_;
        int ans = z;
        while (lft <= rgt) {
            ll mid = (lft + rgt) >> 1;  // 추가 게임횟수 
            ll per = (y + mid) * 100 / (x + mid);
            if (per > z) {
                rgt = mid - 1;
            }
            else
                lft = mid + 1;
        }
        if (lft >= MAX_) {
            cout << -1 << '\n';
        }
        else
            cout << lft << '\n';
    }
    return 0;
}


저작자표시

'PS) BOJ > Binary Search' 카테고리의 다른 글

[C++]수열 걷기[백준 4929]  (0) 2018.08.21
[C++] 랜선 자르기 [BOJ 1654]  (0) 2018.08.16
[C++] K번째 수[백준 1300]  (0) 2018.08.16
[C++]입국심사[백준 3079]  (0) 2018.08.15

전형적인 세그먼트 트리 문제인데 함정은 쿼리에 무조건 작은수~큰수라는 조건이 없으므로 
조건으로 잘 처리해주면 금방 풀수 있는 문제이다. 
바텀업 세그먼트 트리를 구현해서 풀었다. 

구간합 구하기 문제는 역시 세그먼트 트리 구현해서 푸는게 짱인거같다...
(내가 아는선에서는... ㅎ)

시간복잡도는 M*NlogN 만큼 소요되는것같다. 
주어지는 쿼리의 수가 10만턴정도이니 입출력을 줄여주는것도 시간을 충분히 줄여준다. 

참고로 덧셈과정에서 정수형을 넘어갈수 있으니 long long을 사용했다.

스티커 이미지

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

1275번: 커피숍2
1275번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 커피숍2 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 2852 596 419 19.886% 문제 모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.) 어느날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다. 그 게임은 다음과 같은 규칙을 갖는다. N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은
www.acmicpc.net


<Code>


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
//pda_pro12
#include<algorithm>
#include<iostream>
 
#define N_ 100000
#define INT 0x7fff0000
 
using namespace std; 
 
typedef long long ll;
ll a[N_], seg[N_ * 4], n, q; 
 
void init(int node, int x, int y) {
    if (x == y) {
        seg[node] = a[x]; 
        return; 
    }
    int mid = (x + y) >> 1; 
    init(node << 1, x, mid); 
    init((node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] + seg[(node << 1) + 1];
    return; 
}
 
void update(int pos, int val, int node, int x, int y) {
    if (pos < x || pos > y) return; 
    if (x==y) {
        seg[node] = val; 
        return; 
    }
    ll mid = (x + y) >> 1; 
    update(pos, val, node << 1, x, mid); 
    update(pos, val, (node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] + seg[(node << 1) + 1]; 
    return; 
}
 
ll query(int lo, int hi, int node, int x, int y) {
    if (lo > y || hi < x) return 0; 
    if (lo <= x && y <= hi) return seg[node]; 
    ll mid = (x + y) >> 1; 
    ll l = query(lo, hi, node << 1, x, mid); 
    ll r = query(lo, hi, (node << 1) + 1, mid + 1, y);
    return l+r; 
}
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
 
    cin >> n >> q; 
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    init(1, 1, n); 
    while (q--) {
        int a, b, c, d; 
        cin >> a >> b >> c >> d;
        int a1 = (a > b) ? b : a; int b1 = (a > b) ? a : b; 
        cout << query(a1, b1, 1, 1, n) << '\n'; 
        update(c, d, 1, 1, n);
    }
    return 0; 
}


저작자표시

'PS) BOJ > Segment Tree' 카테고리의 다른 글

[C++] 커피숍2 [백준 1275]  (0) 2018.08.17
[C++]음주 코딩[백준 5676]  (0) 2018.08.16

+ Recent posts

티스토리툴바