#include <iostream>

using namespace std;

typedef long long ll;

int n,m;
int tb1[100001];
int main(void)
{
    cin >> n >> m;
    for(int i=0;i<m;++i){
        cin >> tb1[i];
    }
    if(n<=m){
        cout << n << endl;
        return 0;
    }
    ll left = 0;
    ll right = 2000000000LL * 1000000LL ;
    ll mid;
    while(left <= right){
        mid = (left + right) / 2;
        //cout << mid << endl;

        ll st_cnt = 0;
        ll st_cnt_min = 0;
        st_cnt = m;
        for(int i=0;i<m;++i){
            st_cnt += mid / tb1[i];
        }
        st_cnt_min = st_cnt;
        for(int i=0;i<m;++i){
            if(mid % tb1[i] == 0){
                st_cnt_min--;
            }
        }    
        
        st_cnt_min++;
        if(n > st_cnt){
            left = mid + 1;
            
        }
        else if(n < st_cnt_min){
            right = mid - 1;
        }
        else{
            for(int i=0;i<m;++i){
                if(mid % tb1[i] == 0){
                    if(n == st_cnt_min){
                        cout << i+1;
                        return 0;
                    }
                    st_cnt_min++;
                }
            }
        }
    }
    return 0;
}


'알고리즘' 카테고리의 다른 글

[BS] 백준 2512 예산  (0) 2018.04.29
[BS] 백준 1939 중량제한  (0) 2018.04.29
[BS] 백준 3020 개똥벌레  (0) 2018.04.29
[BS] 백준 1300 k번째 수  (0) 2018.04.29
[BS] 백준 3079 입국심사  (0) 2018.04.29

  • 풀고나면 쉽지만 풀기까지 힘든 문제.
  • n을 0~n/2-1로 하지말고 1 ~ n/2 로 하는 방법도 있다. 

개똥벌레 성공


시간 제한
메모리 제한
제출
정답
맞은 사람
정답 비율
1 초
128 MB
2775
981
718
38.151%

문제
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.
아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)
이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.
위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)
하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.
동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이 때, 개똥벌레가 파괴해야하는 장애물의 최소값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)
다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.
출력
첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최소값과 그러한 구간의 수를 공백으로 구분하여 출력한다.
예제 입력 1 
14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3
예제 출력 1 
7 2



















































































#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int err = -99999999;
int up[100001]; // 종유석
int dn[100001]; // 석순
int n, h;
int upc(int tph) { // temp h
       int left = 0;
       int right = n / 2 - 1;
       while (left <= right) {
              int mid = (left + right) / 2;
              if (up[mid] >= tph) {
                     right = mid - 1;
              }
              else {
                     left = mid + 1;
              }
       }
       return n / 2 - left;
}
int dnc(int tph) {
       int left = 0;
       int right = n / 2 - 1;
       while (left <= right) {
              int mid = (left + right) / 2;
              if (dn[mid] >= tph) {
                     right = mid - 1;
              }
              else {
                     left = mid + 1;
              }
       }
       return n / 2 - left;
}
int main(void)
{
       cin >> n >> h;
       for (int i = 0; i<n / 2; ++i) {
              cin >> up[i];
              cin >> dn[i];
       }
       sort(up, up + n / 2);
       sort(dn, dn + n / 2);
       int minval = 999999;
       int mincnt = 1;
       for (int i = 1; i <= h; ++i) {
              int temp = upc(i) + dnc(h - i + 1);
              if (temp == minval) {
                     mincnt++;
              }
              else if (temp < minval) {
                     mincnt = 1;
                     minval = temp;
              }
       }
       cout << minval << ' ' << mincnt << endl;
       return 0;
}






'알고리즘' 카테고리의 다른 글

[BS] 백준 1939 중량제한  (0) 2018.04.29
[BS] 백준 1561 놀이공원  (0) 2018.04.29
[BS] 백준 1300 k번째 수  (0) 2018.04.29
[BS] 백준 3079 입국심사  (0) 2018.04.29
[BS] 백준 2792 보석 상자  (0) 2018.04.29

  • n 제한도 잘 생각해야하고 잘 생각하자
  • 다시한번 상기시키지만 left 조건에 = 없이 써야한다. 3079 문제 참고


K번째 수 성공


시간 제한
메모리 제한
제출
정답
맞은 사람
정답 비율
2 초
128 MB
2302
705
522
35.104%

문제
세준이는 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번째 원소를 출력한다.
예제 입력 1 
3
7
예제 출력 1 
6










































#include <iostream>
#include <limits.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll Imax = 1000000000000000000ll;
int main(void)
{
       ll n, k;
       cin >> n >> k;
       ll left = 0;
       ll right = min(n*n, 1000000000ll);
       while (left <= right) {
              ll mid = (left + right) / 2;
              ll cnt = 0;
              for (int i = 1; i <= n; ++i) {
                     cnt += min(mid / i, n);
              }
              if (cnt < k) {
                     left = mid + 1;
              }
              else {
                     right = mid - 1;
              }
       }
       cout << left << endl;
       return 0;
}


'알고리즘' 카테고리의 다른 글

[BS] 백준 1561 놀이공원  (0) 2018.04.29
[BS] 백준 3020 개똥벌레  (0) 2018.04.29
[BS] 백준 3079 입국심사  (0) 2018.04.29
[BS] 백준 2792 보석 상자  (0) 2018.04.29
[BS] 백준 1477 휴게소 세우기  (0) 2018.04.29

  • INT64_MAX 쓸때는 조심. 중간에 이 값에다가 +1만 하더라도 오버플로우
  • 해법 = > 1000000000000000000LL 을 쓰던가 여기서 98765... 을 쓰면 된다. 
  • 더하는 경우가 처음에 left = 0 + right = max 밖에 없어서 오버플로우 안 날것 같은데 그래도 몰라서 right - 100 하고 했는데도 오버플로우
  • 오버플로우 나는 이유! left + right 할때 오버플로우가 난다. left + (right - left) / 2 를 하면 나지 않는다. 
  • 아무생각없이 right 조건에서 sum >= k 이렇게 썼는데 =을 어디다 넣냐는 중요하다. 보통 sum < k 로 left 조건에 =을 떼고 한다. 

입국심사 성공


시간 제한
메모리 제한
제출
정답
맞은 사람
정답 비율
1 초
128 MB
3148
973
634
27.758%

문제
상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.
가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.
상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.
예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.
상근이와 친구들이 심사를 받는데 걸리는 시간의 최소값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)
다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)
출력
첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최소값을 출력한다. 
예제 입력 1 
2 6
7
10
예제 출력 1 
28




























































#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
typedef long long ll;
ll n, k;
int main(void)
{
       cin >> n >> k;
       vector<ll> tb1(n);
       for (int i = 0; i<n; ++i) {
              cin >> tb1[i];
       }
       ll left = 0;
       ll right = 1000000000000000000LL;
       ll mid;
       while (left <= right) {
              mid = (left + right) / 2;
              ll sum = 0;
              for (int i = 0; i<n; ++i) {
                     sum += mid / tb1[i];
              }
              if (sum >= k) {
                     right = mid - 1;
              }
              else {
                     left = mid + 1;
              }
       }
       cout << left << endl;
       return 0;
}


'알고리즘' 카테고리의 다른 글

[BS] 백준 3020 개똥벌레  (0) 2018.04.29
[BS] 백준 1300 k번째 수  (0) 2018.04.29
[BS] 백준 2792 보석 상자  (0) 2018.04.29
[BS] 백준 1477 휴게소 세우기  (0) 2018.04.29
[BS] 백준 6236 용돈 관리  (0) 2018.04.29

  • 최대로 나누어 준다고 가정하고 풀면 되는 문제
  • 왜냐하면 일단 최대로 나눠줄 수 있으면 못 나눠준 것 들은 최대로 나눠 준 것에서 한개씩만 빼서 줘도 결과엔 영향이 없기 때문이다.


#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long ll;
ll tb1[300001];
ll allsum = 0;
ll maxv = 0;
ll n, m;
//int maxidx;
bool ok(ll mid) {
       ll sum = 0;
       for (int i = 0; i < m; ++i) {
              sum += (tb1[i] - 1) / mid + 1; // tb1[i] -1 한다음 다시 +1 => 홀수 처리
       }
       return sum <= n;
}
int main(void) {
       
       cin >> n >> m;
       for (int i = 0; i<m; ++i) {
              cin >> tb1[i];
              allsum += tb1[i];
              maxv = max(maxv, tb1[i]);
       }
       ll left = 1;
       ll right = maxv;
       while (left <= right) {
              int mid = left + (right - left) / 2;
              if (ok(mid)) {
                     right = mid-1;
              }
              else {
                     left = mid + 1;
              }
       }
       cout << left << endl;
       return 0;
}


'알고리즘' 카테고리의 다른 글

[BS] 백준 1300 k번째 수  (0) 2018.04.29
[BS] 백준 3079 입국심사  (0) 2018.04.29
[BS] 백준 1477 휴게소 세우기  (0) 2018.04.29
[BS] 백준 6236 용돈 관리  (0) 2018.04.29
[BS] 백준 2343 기타레슨  (0) 2018.04.29

  • 교훈. 문제는 나한테 있다. 이분 탐색 알고리즘에겐 없다. 
  • 처음 0과 마지막 l 을 배열에 넣어야 하는 것을 간과해서 시간을 많이 썼다. 
#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;
int tb1[100001];
//int maxidx;
int main(void) {
       
       int n, m, l;
       cin >> n >> m >> l;
       for (int i = 1; i <= n; ++i) {
              cin >> tb1[i];
       }
       tb1[n+1] = l;
       sort(tb1, tb1 + n + 2);
       int left = 1;
       int right = l-1;
       while (left <= right) {
              int mcnt = 0;
              int mid = left + (right - left) / 2;
              //cout << mid << endl;
              for (int i = 1; i <= n+1; ++i) {
                     if (tb1[i] - tb1[i - 1] > mid) {
                           mcnt += ((tb1[i] - tb1[i - 1] - 1)) / mid;
                     }
              }
              if (mcnt > m) {
                     left = mid + 1;
              }
              else {
                     right = mid - 1;
              }
       }
       
       cout << left << endl;
       return 0;
}



'알고리즘' 카테고리의 다른 글

[BS] 백준 3079 입국심사  (0) 2018.04.29
[BS] 백준 2792 보석 상자  (0) 2018.04.29
[BS] 백준 6236 용돈 관리  (0) 2018.04.29
[BS] 백준 2343 기타레슨  (0) 2018.04.29
[BF] 완전탐색 1018 체스판 다시 칠하기  (0) 2018.04.29

  • 푸는데 3시간 걸렸다. 
  • 문제를 잘못읽어서 
  • 제대로 읽고 20분 정도만에 fail 코드를 작성했는데 도저히 
정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.
  • 이 경우를 처리할 방법을 모르겠었다. 


  • 좀 더 보니까 알겠다 저 fail 코드에 제일 아래에 쓴 코드 로 바꾸면 된다. 바보다 위는 고려안해도 되네

  • 이 분의 코드는 저런 걸 다르게 언더플로우 걱정없이 할 수 있게 쓰는 코드라고 배울 수 있을 것 같다. 




#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef int ll;
ll tb1[100001];
int n, m;
// ll go(ll nn){ fail
//     ll cnt = 1;
//     int account = nn;
//     for(int i=0;i<n;++i){
//            if(account - tb1[i] >= 0){
//                   account -= tb1[i];
//            }
//            else{
//                   cnt++;
//                   account = nn;
//            }
//     }
//     return cnt;
// }
ll go(ll nn) {
       ll cnt = 1;
       int account = 0;
       for (int i = 0; i<n; ++i) {
              if (account + tb1[i] > nn) {
                     cnt++;
                     account = tb1[i];
              }
              else {
                     account += tb1[i];
              }
       }
       return cnt;
}
int main(void) {
       ll sum = 0, maxv = 0;
       cin >> n >> m;
       for (int i = 0; i<n; ++i) {
              cin >> tb1[i];
              maxv = max(maxv, tb1[i]);
       }
       ll left = maxv;
       ll right = 1987654321; // large value
       while (left <= right) {
              ll mid = (left + right) / 2; // mid는 정한 가격
                                                               //cout << mid << endl;
              int tempv = go(mid);
              if (tempv > m) {
                     left = mid + 1;
              }
              else {
                     right = mid - 1;
              }
       }
       cout << left << endl;
       return 0;
}



// ll go(ll nn){ 
//     ll cnt = 1;
//     int account = nn;
//     for(int i=0;i<n;++i){
//            if(account - tb1[i] >= 0){
//                   account -= tb1[i];
//            }
//            else{
//                   cnt++;
//                   account = nn - tb1[i];
//            }
//     }
//     return cnt;
// }



  • left를 maxv로 하지 않고 1로하면 에러가 난다.
  • 문제만 읽고서는 maxv를 반드시 사용해야할 필요는 모르겠는데 이로인해 에러가 난다. 
#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;
int tb1[100001];
int sum = 0;
int n, m;
int maxv = 0;
//int maxidx;
int go(int k) {
       int temp = k;
       int cnt = 1;
       for (int i = 0; i < n; ++i) {
              int noo = temp - tb1[i];
              if (noo >= 0) {
                     temp = noo;
              }
              else {
                     temp = k - tb1[i];
                     cnt++;
              }
       }
       return cnt;
}
int main(void) {
       
       cin >> n >> m;
       for (int i = 0; i < n; ++i) {
              cin >> tb1[i];
              sum += tb1[i];
              maxv = max(maxv, tb1[i]);
       }
       
       int left = maxv;
       int right = sum;
       while (left <= right) {
              int mid = left + (right - left) / 2;
              //cout << mid << endl;
              if (go(mid) > m) {
                     left = mid + 1;
              }
              else {
                     right = mid - 1;
              }
       }
       
       cout << left << endl;
       return 0;
}


for문 구현
#include <iostream>
#include <algorithm>

using namespace std;

char table[1001][1001];


int find(int starti,int startj)
{
    int cnt = 0;//B start
    int cnt2 = 0;//W start

    for (int i = starti; i < starti+8; ++i) {
        for (int j = startj; j < startj + 8; ++j) {
            if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
                if (table[i][j] == 'W') {
                    cnt++;
                }
            }
            if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
                if (table[i][j] == 'B') {
                    cnt++;
                }
            }
            if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
                if (table[i][j] == 'B') {
                    cnt2++;
                }
            }
            if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
                if (table[i][j] == 'W') {
                    cnt2++;
                }
            }
        }
    }

    return min(cnt, cnt2);
    
}


int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> table[i][j];
        }
    }
    int ret = INT32_MAX;
    for (int i = 0; i < n - 7; ++i) {
        for (int j = 0; j < m - 7; ++j) {
            ret = min(ret,find(i, j));
        }
    }
    cout << ret << endl;
    return 0;
}


재귀로 구현
#include <iostream>
#include <algorithm>

using namespace std;

char table[1001][1001];

int Bfind(int i, int j,int ans,int sti,int stj) {
    //cout << " i : " << i << "j : " << j << " ans : " << ans << " char : " << table[i][j] << '\n';
    if (j == stj+8) {
        return ans;
    }
    if (i == sti+8) {
        return Bfind(i-8,j+1,ans,sti,stj);
    }
    

    if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
        if (table[i][j] == 'W') {
            ans++;
        }
    }

    if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
        if (table[i][j] == 'B') {
            ans++;
        }
    }
    Bfind(i + 1, j, ans,sti,stj);
}

int Wfind(int i, int j, int ans,int sti,int stj) {
    //cout << " i : " << i << "j : " << j << " ans : " << ans << " char : " << table[i][j] << '\n';
    if (j == stj+8) {
        return ans;
    }
    if (i == sti+8) {
        return Wfind(i - 8, j + 1, ans,sti,stj);
    }


    if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
        if (table[i][j] == 'B') {
            ans++;
        }
    }
    if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
        if (table[i][j] == 'W') {
            ans++;
        }
    }
    Wfind(i + 1, j, ans,sti,stj);
}

int find(int starti,int startj)
{
    int cnt = 0;//B start
    int cnt2 = 0;//W start
    cnt = Bfind(starti, startj, 0,starti,startj);
    cnt2 = Wfind(starti, startj, 0,starti,startj);

    //cout << cnt << ' ' << cnt2 << endl;
    return min(cnt, cnt2);
    
}


int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> table[i][j];
        }
    }

    int ret = INT32_MAX;
    for (int i = 0; i < n - 7; ++i) {
        for (int j = 0; j < m - 7; ++j) {
            ret = min(ret,find(i, j));
        }
    }
    cout << ret << endl;
    return 0;
}


'알고리즘' 카테고리의 다른 글

[BS] 백준 6236 용돈 관리  (0) 2018.04.29
[BS] 백준 2343 기타레슨  (0) 2018.04.29
[BF] 백준 2775 부녀회장이 될 테야  (0) 2018.04.29
[DP] 백준 2631 줄세우기  (0) 2018.04.29
[DP] 백준 5557 1학년  (0) 2018.04.29


#include <iostream>

using namespace std;

int go(int a,int b){
    int sum = 0;
    if(a==0){
        return b;
    }
    for(int i=1;i<=b;++i){
        sum += go(a-1,i);
    }
    return sum;
}

int main(void){
    int t;
    cin >> t;
    while(t--){
        int a, b;
        cin >> a >> b;
        cout << go(a,b) << '\n';
    }
    return 0;
}


'알고리즘' 카테고리의 다른 글

[BS] 백준 2343 기타레슨  (0) 2018.04.29
[BF] 완전탐색 1018 체스판 다시 칠하기  (0) 2018.04.29
[DP] 백준 2631 줄세우기  (0) 2018.04.29
[DP] 백준 5557 1학년  (0) 2018.04.29
[DP] 백준 10164 격자상의경로  (0) 2018.04.29

+ Recent posts