Hello Ocean! ๐ŸŒผ

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ž…๊ตญ ์‹ฌ์‚ฌ ๋ณธ๋ฌธ

Algorithm

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ž…๊ตญ ์‹ฌ์‚ฌ

bba_dda 2020. 9. 7. 19:41
๋ฐ˜์‘ํ˜•

๋ฌธ์ œ ์„ค๋ช…

n๋ช…์ด ์ž…๊ตญ์‹ฌ์‚ฌ๋ฅผ ์œ„ํ•ด ์ค„์„ ์„œ์„œ ๊ธฐ๋‹ค๋ฆฌ๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ์ž…๊ตญ์‹ฌ์‚ฌ๋Œ€์— ์žˆ๋Š” ์‹ฌ์‚ฌ๊ด€๋งˆ๋‹ค ์‹ฌ์‚ฌํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์€ ๋‹ค๋ฆ…๋‹ˆ๋‹ค.

์ฒ˜์Œ์— ๋ชจ๋“  ์‹ฌ์‚ฌ๋Œ€๋Š” ๋น„์–ด์žˆ์Šต๋‹ˆ๋‹ค. ํ•œ ์‹ฌ์‚ฌ๋Œ€์—์„œ๋Š” ๋™์‹œ์— ํ•œ ๋ช…๋งŒ ์‹ฌ์‚ฌ๋ฅผ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ€์žฅ ์•ž์— ์„œ ์žˆ๋Š” ์‚ฌ๋žŒ์€ ๋น„์–ด ์žˆ๋Š” ์‹ฌ์‚ฌ๋Œ€๋กœ ๊ฐ€์„œ ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ ๋” ๋นจ๋ฆฌ ๋๋‚˜๋Š” ์‹ฌ์‚ฌ๋Œ€๊ฐ€ ์žˆ์œผ๋ฉด ๊ธฐ๋‹ค๋ ธ๋‹ค๊ฐ€ ๊ทธ๊ณณ์œผ๋กœ ๊ฐ€์„œ ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์„ ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.

๋ชจ๋“  ์‚ฌ๋žŒ์ด ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ์ตœ์†Œ๋กœ ํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.

์ž…๊ตญ์‹ฌ์‚ฌ๋ฅผ ๊ธฐ๋‹ค๋ฆฌ๋Š” ์‚ฌ๋žŒ ์ˆ˜ n, ๊ฐ ์‹ฌ์‚ฌ๊ด€์ด ํ•œ ๋ช…์„ ์‹ฌ์‚ฌํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์ด ๋‹ด๊ธด ๋ฐฐ์—ด times๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ชจ๋“  ์‚ฌ๋žŒ์ด ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์˜ ์ตœ์†Ÿ๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

์ž…๊ตญ์‹ฌ์‚ฌ๋ฅผ ๊ธฐ๋‹ค๋ฆฌ๋Š” ์‚ฌ๋žŒ์€ 1๋ช… ์ด์ƒ 1,000,000,000๋ช… ์ดํ•˜์ž…๋‹ˆ๋‹ค.
๊ฐ ์‹ฌ์‚ฌ๊ด€์ด ํ•œ ๋ช…์„ ์‹ฌ์‚ฌํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์€ 1๋ถ„ ์ด์ƒ 1,000,000,000๋ถ„ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
์‹ฌ์‚ฌ๊ด€์€ 1๋ช… ์ด์ƒ 100,000๋ช… ์ดํ•˜์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

n times return
6 [7, 10] 28

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

๊ฐ€์žฅ ์ฒซ ๋‘ ์‚ฌ๋žŒ์€ ๋ฐ”๋กœ ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์œผ๋Ÿฌ ๊ฐ‘๋‹ˆ๋‹ค.

7๋ถ„์ด ๋˜์—ˆ์„ ๋•Œ, ์ฒซ ๋ฒˆ์งธ ์‹ฌ์‚ฌ๋Œ€๊ฐ€ ๋น„๊ณ  3๋ฒˆ์งธ ์‚ฌ๋žŒ์ด ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์Šต๋‹ˆ๋‹ค.

10๋ถ„์ด ๋˜์—ˆ์„ ๋•Œ, ๋‘ ๋ฒˆ์งธ ์‹ฌ์‚ฌ๋Œ€๊ฐ€ ๋น„๊ณ  4๋ฒˆ์งธ ์‚ฌ๋žŒ์ด ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์Šต๋‹ˆ๋‹ค.

14๋ถ„์ด ๋˜์—ˆ์„ ๋•Œ, ์ฒซ ๋ฒˆ์งธ ์‹ฌ์‚ฌ๋Œ€๊ฐ€ ๋น„๊ณ  5๋ฒˆ์งธ ์‚ฌ๋žŒ์ด ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์Šต๋‹ˆ๋‹ค.

20๋ถ„์ด ๋˜์—ˆ์„ ๋•Œ, ๋‘ ๋ฒˆ์งธ ์‹ฌ์‚ฌ๋Œ€๊ฐ€ ๋น„์ง€๋งŒ 6๋ฒˆ์งธ ์‚ฌ๋žŒ์ด ๊ทธ๊ณณ์—์„œ ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์ง€ ์•Š๊ณ  1๋ถ„์„ ๋” ๊ธฐ๋‹ค๋ฆฐ ํ›„์— ์ฒซ ๋ฒˆ์งธ ์‹ฌ์‚ฌ๋Œ€์—์„œ ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์œผ๋ฉด 28๋ถ„์— ๋ชจ๋“  ์‚ฌ๋žŒ์˜ ์‹ฌ์‚ฌ๊ฐ€ ๋๋‚ฉ๋‹ˆ๋‹ค.

ํ’€์ด

๋ฌธ์ œ์˜ ์นดํ…Œ๊ณ ๋ฆฌ๊ฐ€ ์ด๋ถ„ํƒ์ƒ‰ ์ด๊ธฐ๋„ ํ–ˆ์ง€๋งŒ, ์ž…๋ ฅ ๋ฒ”์œ„๋ฅผ ๋ณด์•˜์„ ๋•Œ ์™„์ „ํƒ์ƒ‰์œผ๋กœ๋Š” ์•ˆ๋˜๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค.
๋”ฐ๋ผ์„œ ์ด๋ถ„ํƒ์ƒ‰์œผ๋กœ ํ’€์ดํ–ˆ๋‹ค.

 

์ฝ”๋“œ

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

unsigned long long solution(int n, vector<int> times) {
    unsigned long long answer = 987654321;
    unsigned long long left = 0; 
    unsigned long long mid = 0;
    sort(times.begin(), times.end());
    unsigned long long right = times[times.size()-1]*n; //์ตœ๋Œ“๊ฐ’
    answer = right;

    while (left <= right){
        unsigned long long done = 0;
        mid = (left + right) /2 ;
        for (int time:times){
            done += mid/time;
        }
        if (done < n) //์ฃผ์–ด์ง„ ์‹œ๊ฐ„๋™์•ˆ ์‹ฌ์‚ฌ ์™„๋ฃŒ x
            left = mid + 1; //์‹œ๊ฐ„ ๋Š˜๋ฆฌ๊ธฐ 
        else { //์ฃผ์–ด์ง„ ์‹œ๊ฐ„์ด ์ถฉ๋ถ„ ํ˜น์€ ๋”ฑ ๋งž๋Š” ๊ฒฝ์šฐ
            if (mid < answer) //๊ฐ€์žฅ ๋”ฑ ๋งž๋Š” ์‹œ๊ฐ„์„ ์ฐพ๊ธฐ ์œ„ํ•ด 
                answer = mid;
            right = mid-1; 
        }
    }
    return answer;
}

 

 


 

24๋…„ 8์›”์— ๋‹ค์‹œ ํ’€์–ด๋ดค์Šต๋‹ˆ๋‹ค! (with Python)

 

Solution.

  • ์ž…๋ ฅ์˜ ๋ฒ”์œ„๊ฐ€ ํฌ๊ธฐ ๋•Œ๋ฌธ์—, ์™„์ „ํƒ์ƒ‰์ด ์•„๋‹ˆ๋ผ ์ด๋ถ„ํƒ์ƒ‰์„ ์‚ฌ์šฉํ•ด์•ผ ํ•œ๋‹ค.
  • ๋ชจ๋“  ์‚ฌ๋žŒ๋“ค์ด ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›๊ธฐ ์œ„ํ•œ ์ตœ์†Œ์˜ ์‹œ๊ฐ„์„ ํƒ์ƒ‰
  • 0 ~ ์ตœ๋Œ“๊ฐ’ ์‚ฌ์ด๋ฅผ ์ด๋ถ„ํƒ์ƒ‰
    • ์ตœ๋Œ“๊ฐ’์€ ์–ด๋–ป๊ฒŒ ๊ตฌํ•ด์•ผ ํ•˜๋Š”๊ฐ€?
      • ๋ณดํ†ต n๋ช… * max์‹ฌ์‚ฌ์‹œ๊ฐ„ ์„ ์ตœ๋Œ“๊ฐ’์œผ๋กœ ์„ค์ •ํ•˜๊ณ  ํ’€์ดํ•˜๋Š” ๊ฒƒ ๊ฐ™์Œ (๊ณผ๊ฑฐ์˜ ๋‚˜๋„...)
    • ํ•˜์ง€๋งŒ, ๊ฐ€์žฅ ์ตœ์†Œ์˜ ์ตœ๋Œ“๊ฐ’!์€
      • n๋ช…/์‹ฌ์‚ฌ๊ด€ ์ˆ˜ * max์‹ฌ์‚ฌ์‹œ๊ฐ„
      • ๋ชจ๋“  ์‹ฌ์‚ฌ๊ด€์—๊ฒŒ n๋ช…์„ ๊ณ ๋ฅด๊ฒŒ ๋ถ„ํฌํ•˜๋ฉด, ์‹ฌ์‚ฌ๊ด€ ๋‹น n๋ช…/์‹ฌ์‚ฌ๊ด€ ์ˆ˜ ์˜ ์‚ฌ๋žŒ์„ ๋ฐฐ์ •๋ฐ›๊ธฐ ๋•Œ๋ฌธ
      • ๋‘ ๊ฒฝ์šฐ๋ฅผ ๋ชจ๋‘ ์‹คํ–‰์‹œ์ผœ๋ณด์•˜๋Š”๋ฐ, ํ…Œ์ŠคํŠธ3๋ฒˆ์„ ์ œ์™ธํ•˜๊ณ  ์†Œ์š”์‹œ๊ฐ„์ด ์ ์€ ๊ฒƒ์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค. 
        • ์†Œ์š”์‹œ๊ฐ„ : n๋ช…/์‹ฌ์‚ฌ๊ด€ ์ˆ˜ * max์‹ฌ์‚ฌ์‹œ๊ฐ„ < n๋ช… * max์‹ฌ์‚ฌ์‹œ๊ฐ„ 

์ตœ๋Œ“๊ฐ’ : n * max(times)

 

์ตœ๋Œ“๊ฐ’ : (n // len(times) * max(times)

def solution(n, times):
    left = 0
    right = (n // len(times)) * max(times)
    answer = right
    
    while left <= right:
        mid = (left + right) // 2
        done = 0
        for t in times:
            done += mid//t
        if done >= n: # ๊ฒ€์‚ฌ์™„๋ฃŒ
            answer = min(answer, mid)
            right = mid - 1
        else: # ์‹คํŒจ
            left = mid + 1
    return answer

 

๋ฐ˜์‘ํ˜•