백준 - 15732 도토리 숨기기

문제 링크입니다 : https://www.acmicpc.net/problem/15732

15732번: 도토리 숨기기

 

이분탐색 문제이다.

 

 

마지막 도토리가 들어있는 상자의 번호 몇번인지 결정문제로 바꾸어서 풀면 되는데,

상자들은 일정한 간격으로 도토리를 넣기 때문에 나누기를 이용하면 간단하게 임의로 정한 도토리 숫자번호까지 들어간 도토리의 개수를 알 수 있다.

 

 

그리고 임의로 잡은 숫자가 도토리 넣는 규칙의 A(도토리 넣는 시작점)보다 작다면 그 규칙에서는 도토리를 아하나도 안 넣어야 한다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

struct Rule {
    ll A, B, C;
};

int N, K, D;
vector<Rule> rules;


ll getAcornNum(ll mid) {
    ll ret = 0;

    for(const auto& rule : rules) {
        ll temp = min(rule.B, mid) - rule.A;
        if(temp < 0) {
            continue;
        } else {
            ret += temp / rule.C + 1;
        }
    }

    return ret;
}

int main() {
    cin >> N >> K >> D;
    rules.resize(K);

    ll low = N;
    ll high = 0;
    for(int i = 0; i < K; i++) {
        cin >> rules[i].A >> rules[i].B >> rules[i].C;
        if(rules[i].A < low) {
            low = rules[i].A;
        }
        if(rules[i].B > high) {
            high = rules[i].B;
        }
    }

    ll mid, result;

    while(low <= high) {
        mid = (low + high) / 2;

        ll acornNum = getAcornNum(mid);

        if(acornNum >= D) {
            high = mid - 1;
            result = mid;
        } else {
            low = mid + 1;
        }
    }

    cout << result;

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~