BOJ 15732 도토리 숨기기

사용한 알고리즘

이분탐색

알고리즘 설명

역시 이분탐색은 처음에 감을 잡기 어려운 것 같다.
하나씩 넣어서 새어보는 형태로는 시간초과로 불가능하다.
여기서 중요한 개념은 마지막 상자를 정해 놓고 했을때, 각 패턴에서 가지는 상자수가 계산가능하다는 점이다.
또한 이분탐색의 중요한 관점중 하나는 마지막 상자번호가 클수록, 넣어야 하는 도토리 수가 증가한다는 것 바로 선형성을 가진다는 것이다.
이 두가지 점에서 마지막 상자 번호라는 값을 이용하여 탐색 가능하다.
일단 이분탐색을 알아채기 위해선 선형성을 가짐을 인지하는 것이 중요한것 같다.

풀이

// baekjoon 15732 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 10001;
const int MAX_INF = 1000001;
typedef long long ll;

struct Sequence{
    int start, end, step;
    Sequence():Sequence(0,0,0){}
    Sequence(int start, int end, int step):start(start), end(end), step(step){}
    ll getPos(int pos) {
        if (pos < start) return 0;
        return (min(pos, end) - start)/step + 1;
    }
};

int N, K, ret;
ll D;
Sequence seq[MAX_N];

ll getIdx(int pos) {
    ll cnt = 0;
    for (int i=0; i<K; i++)
        cnt += seq[i].getPos(pos);
    return cnt;
}

int main() {
    scanf("%d%d%lld", &N, &K, &D);
    for (int i = 0; i < K; ++i) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        seq[i] = Sequence(x, y, z);
    }

    int ret = MAX_INF;
    ll left = 0, right = MAX_INF;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (D <= getIdx(mid)) {
            ret = min(ret, mid);
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    printf("%d\n", ret);
    return 0;
}