๐Ÿ•๏ธ ICPC Sinchon/Binary Search

[BOJ][C++] ๋ฐฑ์ค€ 1654๋ฒˆ: ๋žœ์„  ์ž๋ฅด๊ธฐ

์„ ๋‹ฌ 2023. 11. 17. 01:51
๋ฐ˜์‘ํ˜•

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

 

1654๋ฒˆ: ๋žœ์„  ์ž๋ฅด๊ธฐ

์ฒซ์งธ ์ค„์—๋Š” ์˜ค์˜์‹์ด ์ด๋ฏธ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋žœ์„ ์˜ ๊ฐœ์ˆ˜ K, ๊ทธ๋ฆฌ๊ณ  ํ•„์š”ํ•œ ๋žœ์„ ์˜ ๊ฐœ์ˆ˜ N์ด ์ž…๋ ฅ๋œ๋‹ค. K๋Š” 1์ด์ƒ 10,000์ดํ•˜์˜ ์ •์ˆ˜์ด๊ณ , N์€ 1์ด์ƒ 1,000,000์ดํ•˜์˜ ์ •์ˆ˜์ด๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํ•ญ์ƒ K โ‰ฆ N ์ด๋‹ค. ๊ทธ

www.acmicpc.net

 

๋ฌธ์ œ

์ง‘์—์„œ ์‹œ๊ฐ„์„ ๋ณด๋‚ด๋˜ ์˜ค์˜์‹์€ ๋ฐ•์„ฑ์›์˜ ๋ถ€๋ฆ„์„ ๋ฐ›๊ณ  ๊ธ‰ํžˆ ๋‹ฌ๋ ค์™”๋‹ค. ๋ฐ•์„ฑ์›์ด ์บ ํ”„ ๋•Œ ์“ธ N๊ฐœ์˜ ๋žœ์„ ์„ ๋งŒ๋“ค์–ด์•ผ ํ•˜๋Š”๋ฐ ๋„ˆ๋ฌด ๋ฐ”๋น ์„œ ์˜์‹์ด์—๊ฒŒ ๋„์›€์„ ์ฒญํ–ˆ๋‹ค.

์ด๋ฏธ ์˜ค์˜์‹์€ ์ž์ฒด์ ์œผ๋กœ K๊ฐœ์˜ ๋žœ์„ ์„ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ K๊ฐœ์˜ ๋žœ์„ ์€ ๊ธธ์ด๊ฐ€ ์ œ๊ฐ๊ฐ์ด๋‹ค. ๋ฐ•์„ฑ์›์€ ๋žœ์„ ์„ ๋ชจ๋‘ N๊ฐœ์˜ ๊ฐ™์€ ๊ธธ์ด์˜ ๋žœ์„ ์œผ๋กœ ๋งŒ๋“ค๊ณ  ์‹ถ์—ˆ๊ธฐ ๋•Œ๋ฌธ์— K๊ฐœ์˜ ๋žœ์„ ์„ ์ž˜๋ผ์„œ ๋งŒ๋“ค์–ด์•ผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด 300cm ์งœ๋ฆฌ ๋žœ์„ ์—์„œ 140cm ์งœ๋ฆฌ ๋žœ์„ ์„ ๋‘ ๊ฐœ ์ž˜๋ผ๋‚ด๋ฉด 20cm๋Š” ๋ฒ„๋ ค์•ผ ํ•œ๋‹ค. (์ด๋ฏธ ์ž๋ฅธ ๋žœ์„ ์€ ๋ถ™์ผ ์ˆ˜ ์—†๋‹ค.)

ํŽธ์˜๋ฅผ ์œ„ํ•ด ๋žœ์„ ์„ ์ž๋ฅด๊ฑฐ๋‚˜ ๋งŒ๋“ค ๋•Œ ์†์‹ค๋˜๋Š” ๊ธธ์ด๋Š” ์—†๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๋ฉฐ, ๊ธฐ์กด์˜ K๊ฐœ์˜ ๋žœ์„ ์œผ๋กœ N๊ฐœ์˜ ๋žœ์„ ์„ ๋งŒ๋“ค ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ๋Š” ์—†๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž. ๊ทธ๋ฆฌ๊ณ  ์ž๋ฅผ ๋•Œ๋Š” ํ•ญ์ƒ ์„ผํ‹ฐ๋ฏธํ„ฐ ๋‹จ์œ„๋กœ ์ •์ˆ˜๊ธธ์ด๋งŒํผ ์ž๋ฅธ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž. N๊ฐœ๋ณด๋‹ค ๋งŽ์ด ๋งŒ๋“œ๋Š” ๊ฒƒ๋„ N๊ฐœ๋ฅผ ๋งŒ๋“œ๋Š” ๊ฒƒ์— ํฌํ•จ๋œ๋‹ค. ์ด๋•Œ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋žœ์„ ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์—๋Š” ์˜ค์˜์‹์ด ์ด๋ฏธ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋žœ์„ ์˜ ๊ฐœ์ˆ˜ K, ๊ทธ๋ฆฌ๊ณ  ํ•„์š”ํ•œ ๋žœ์„ ์˜ ๊ฐœ์ˆ˜ N์ด ์ž…๋ ฅ๋œ๋‹ค. K๋Š” 1์ด์ƒ 10,000์ดํ•˜์˜ ์ •์ˆ˜์ด๊ณ , N์€ 1์ด์ƒ 1,000,000์ดํ•˜์˜ ์ •์ˆ˜์ด๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํ•ญ์ƒ K โ‰ฆ N ์ด๋‹ค. ๊ทธ ํ›„ K์ค„์— ๊ฑธ์ณ ์ด๋ฏธ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๊ฐ ๋žœ์„ ์˜ ๊ธธ์ด๊ฐ€ ์„ผํ‹ฐ๋ฏธํ„ฐ ๋‹จ์œ„์˜ ์ •์ˆ˜๋กœ ์ž…๋ ฅ๋œ๋‹ค. ๋žœ์„ ์˜ ๊ธธ์ด๋Š” 231-1๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— N๊ฐœ๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋žœ์„ ์˜ ์ตœ๋Œ€ ๊ธธ์ด๋ฅผ ์„ผํ‹ฐ๋ฏธํ„ฐ ๋‹จ์œ„์˜ ์ •์ˆ˜๋กœ ์ถœ๋ ฅํ•œ๋‹ค.

 

ํ’€์ด

lan ํ•จ์ˆ˜๋Š” length ๊ธธ์ด์˜ ๋žœ์„ ์ด ๋‚˜์˜ค๋Š” ๊ฐฏ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

lan() ๊ฐ’์ด n๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ฒŒ ๋‚˜์˜ค๋Š” length๋“ค์˜ ์ตœ๋Œ“๊ฐ’์„ ๊ตฌํ•˜๋ฉด๋จ.

์ฆ‰ length์— ๋ง‰ ๋Œ€์ž…ํ•ด์„œ ์กฐ๊ฑด์— ๋งž๋Š”๊ฑธ ๊ณจ๋ผ๋‚ด๋ฉด ๋˜๋Š”๋ฐ,

 

์ด ๊ณผ์ •์—์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋‚˜๊ธฐ ๋•Œ๋ฌธ์— ์ด๋ถ„ํƒ์ƒ‰์„ ์‚ฌ์šฉํ•œ๋‹ค

length ๊ธธ์ด๊ฐ’์— ๋Œ€ํ•˜์—ฌ ํ•ด๋‹น ๊ธธ์ด์— ๋‚˜์˜ค๋Š” ๋žœ์„  ๊ฐฏ์ˆ˜๊ฐ€ n๋ณด๋‹ค ์ž‘์œผ๋ฉด ๊ธธ์ด๋ฅผ ๋Š˜๋ฆฌ๊ณ , ํฌ๋ฉด ๊ธธ์ด๋ฅผ ์ค„์ด๋Š” ๋ฐฉ์‹์œผ๋กœ ์ด๋ถ„ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•œ๋‹ค.

 

์ด๋ถ„ํƒ์ƒ‰์„ ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ•˜๋ƒ์— ๋”ฐ๋ผ ๊ทธ ๋””ํ…Œ์ผ์— ๋”ฐ๋ผ ๋ฐ˜๋ก€๊ฐ€ ์ƒ๊ธฐ๋‹ˆ ์ž˜ ์•ˆํ’€๋ฆฐ๋‹ค๋ฉด ์•„๋ž˜ ๊ธ€์„ ์ฐธ๊ณ ํ•˜์ž (๋ฐ˜๋ก€๋ฅผ ์ •๋ง ์ž˜ ์ •๋ฆฌํ•ด์คฌ๋‹ค)

https://www.acmicpc.net/board/view/124982

 

๊ธ€ ์ฝ๊ธฐ - ์ด๋ถ„ํƒ์ƒ‰์„ ์ ‘๊ทผํ•˜๋Š” 3๊ฐ€์ง€ ๋ฐฉ๋ฒ• (๋ฐ˜๋ก€ ํฌํ•จ)

๋Œ“๊ธ€์„ ์ž‘์„ฑํ•˜๋ ค๋ฉด ๋กœ๊ทธ์ธํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

www.acmicpc.net

 

๋งŒ์•ฝ 47%์—์„œ ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค ๋˜๋Š” 49%์—์„œ ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค ๊ฐ€ ๋œฌ๋‹ค๋ฉด

์ด๋ถ„ํƒ์ƒ‰์— ์‚ฌ์šฉํ•˜๋Š” ๋ณ€์ˆ˜๋“ค( start, end, mid )๊ณผ ๋‹ต์— ํ•ด๋‹นํ•˜๋Š” ๋ณ€์ˆ˜์˜ ๋ฒ”์œ„๋ฅผ ํ™•์ธํ•˜์ž

๋žœ์„ ๊ธธ์ด์˜ ๋ฒ”์œ„๊ฐ€ ๋งค์šฐ ํฌ๊ธฐ ๋•Œ๋ฌธ์— ๋žœ์„ ์˜ ๊ธธ์ด์— ๋Œ€์‘ํ•˜๋Š” ๋ณ€์ˆ˜๋“ค(์œ„์— ๋งํ•œ ์ด๋ถ„ํƒ์ƒ‰์— ์‚ฌ์šฉํ•˜๋Š” ๋ณ€์ˆ˜๋“ค๊ณผ ๋‹ต ๋ณ€์ˆ˜)์€ int๋ณด๋‹ค ํฐ ๋ฒ”์œ„์ธ long long์œผ๋กœ ๋”ฐ๋กœ ์ง€์ •์ด ํ•„์š”ํ•˜๋‹ค

 

// ํ’€์ด : https://whkakrkr.tistory.com

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

using namespace std;

int k, n;

int lan(vector<int>&v, int length) {
    int cnt=0;
    for(int i=0; i<k; i++) {
        cnt += v[i]/length;
    }
    return cnt;
}

int main() {
    cin >> k >> n;
    vector<int> v(k);
    for(int i=0; i<k; i++) {
        cin >> v[i];
    }
    
    long long ans=1;
    long long start=1, end=*max_element(v.begin(), v.end());
    while(start<=end) {
        long long mid = (start+end)/2;
        int tmp = lan(v, mid);
        if(tmp < n) {
            end = mid-1;
        } else {
            ans = max(mid, ans);
            start = mid+1;
        }
    }
    cout << ans;
}
๋ฐ˜์‘ํ˜•