중복값 처리와 배열 초기화 때문에 굉장히 애먹은 문제이다....

접근한 방식은 입력받은 하나의 수열값들을 인덱싱을 통해 표시를 해주고(음수값 + 고정 Value처리)

나머지 하나의 수열을 입력받으면서

교차점일 경우에 해당 인덱스 지점까지의 Prefix_Sum값을 비교해주는 것이다. 
(before 교차점까지의 PrefixSum의 차이값 비교)

하지만... 인덱싱 처리해준 값들을 여러테케를 돌리는 문제이다보니 

초기화 해주지 않은 것이 화근이었다...ㅠ

좀더 꼼꼼할 필요가 있는 자신을 돌아보게됨..

스티커 이미지

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

<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
//pda_pro12
#include<algorithm>
#include<iostream>
#include<vector>
 
#define N_ 10001
#define sz(x) x.size()
using namespace std;
 
typedef long long ll; 
typedef double db; 
int a[N_], a1[N_], Prefix[N_], Prefix1[N_], n, m, Num[20002], Sum1, Sum2, ans, before, before1;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    while (cin >> n && n > 0) {
        ans = 0;  before = 0; before1 = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i]; Num[a[i] + 10000] = i;
            Prefix[i] = a[i];
            Prefix[i] += Prefix[i - 1];
        }
        cin >> m;
        for (int i = 1; i <= m; i++) {
            cin >> a1[i];
            Prefix1[i] = a1[i];
            Prefix1[i] += Prefix1[i - 1];
            if (Num[a1[i] + 10000]) {
                int lower_Sum = Num[a1[i] + 10000];
                Sum1 = Prefix[lower_Sum] - Prefix[before];
                Sum2 = Prefix1[i] - Prefix1[before1];
                before1 = i; before = lower_Sum;
                ans += (Sum1 > Sum2) ? Sum1 : Sum2;
            }
        }
        int r = Prefix[n] - Prefix[before];
        int q = Prefix1[m] - Prefix1[before1];
        ans += (r > q) ? r : q;
        cout << ans << '\n';
        for (int i = 0; i <= 20000; i++)
            Num[i] = 0; 
    }
    return 0;
}


저작자표시

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

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

올 초에 이분탐색 개념을 처음 알았을때 어떻게 이분탐색을 꾸역꾸역 끼워넣을지 고민했던 기억이...

생각해보면 무척 간단한거였다. 

문제 해결과정

1. 랜선의 길이의 상한과 하한을 잡아준다. 

2. 랜선의 하한과 상한을 기준으로 중간값을 구해주고 중간값을 길이로 가정하고 몇개의 랜선으로 쪼개  
   질수 있는지 탐색해본다.

<직접 손으로 써서 설명해봤는데 이해가 잘될지 모르겠다>

이렇게 탐색하면 1~최대 2147483647이니깐  NLogK만 끝낼수 있다 
(가정된 길이에 대한 갯수 구하는과정)N*LogK

(상한 하한의 길이만큼을 /2해가면서 탐색하므로 Log길이 만큼이된다.)

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


<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
//pda_pro12
#include<algorithm>
#include<iostream>
#define N_ 10001
#define INT 0x7fff0000
using namespace std;
 
typedef long long ll; 
int k, n, a[N_], Max;    ll lft, rgt; 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
 
    cin >> k >> n; 
    for (int i = 0; i < k; i++) 
        cin >> a[i], Max = max(a[i],Max);             // 보유중인 랜선에 대한 정보를 입력받음 
    int ans = 0; 
    lft = 1;  rgt = Max; 
    while (lft <= rgt) {
        ll mid = (lft + rgt) >> 1; 
        int Sum = 0; 
        for (int i = 0; i < k; i++) 
            Sum += (a[i] / mid); 
        if (Sum >= n) 
            ans = mid,lft = mid + 1;
        else
            rgt = mid - 1; 
    }
    cout << ans; 
    return 0; 
}


저작자표시

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

[C++]수열 걷기[백준 4929]  (0) 2018.08.21
[C++] K번째 수[백준 1300]  (0) 2018.08.16
[C++] 게임 [백준 1072]  (0) 2018.08.16
[C++]입국심사[백준 3079]  (0) 2018.08.15

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

배열 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








입국심사대 N이 10만,   입국 처리인원이 10억으로 Max값이 주어진다. 각 심사대에서 처리하는데 소요되는 시간 또한 10억이다. 완탐으로 1초안에 해결이 불가능한 문제이다. 
이걸 완탐돌린다면... 생각만 해도 끔찍하다. 

착안해낸 아이디어
1. 하한값을 1로 잡고 상한값을 10억*10만값으로 가정하고 풀이하였다.
    (WorstCase: 각 심사대10억*10만)

2.  이분탐색으로 시간을 가정하고 해당 시간으로 10만의 심사대에서 처리하고자하는 인원 M을 처리할
     수 있는지 혹은 처리하기에 시간이 부족한지를 살펴본다. 

3. 처리시간이 부족하다면 하한을 중간값+1로 설정하여 중간값을 다시 설정하고 이분탐색을 진행한다. 
    인원처리가 가능하다면 상한값을 중간값-1로 설정하여 left값이 right를 초과하는 순간 종료된다. 

4. lft는 항상 최소한의 가능한순간까지의 하한값을 증가시킬것이다. right값을 lft값이 초과하는 순간
   빠져나와버리므로 수용가능한 경우의 최소 mid값과 lft값은 일치한다. 
시간 복잡도 :  O(NlogN) 
탐색과정을 보면 다음과 같다 





<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
// pda_pro12
#include<iostream>
#include<algorithm>
#define N_ 100000
#define Upper 100000000000000   // N_ * M(max)
 
using namespace std;
 
typedef long long ll;
ll lft, rgt, n, m;   int a[N_];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        cin >> a[i];
 
    ll lft = 1;  ll rgt = Upper;   // Lower ,  Upper
 
    while (lft <= rgt) {
        
        ll mid = (lft + rgt) >> 1;
        ll Sum = 0;
        for (int i = 0; i < n; i++)
            Sum += (mid / a[i]);
        if (Sum >= m)
            rgt = mid - 1; 
        else
            lft = mid+1;
    }
    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++] 게임 [백준 1072]  (0) 2018.08.16

+ Recent posts

티스토리툴바