# ๐ป ์ด์ง ํ์ by ํ๋ก๊ทธ๋๋จธ์ค ์ฐ์ต๋ฌธ์ 

waterglassesยท2022๋ 3์ 25์ผ
0

## TIL

๋ชฉ๋ก ๋ณด๊ธฐ
5/50

ํธ๋ฆฌ์ ๊ฐ๋๊ณผ ์ํ, ํ, ํธ๋ผ์ด, ์ ๋ ฌ, ์ด์ง ํ์์ ๋ํด์ ๋ฐฐ์ ๋ค. ์ ๋ ฌ ๋ฌธ์  ๊ฐ์ฅ ํฐ ์ ์์๋ 1์๊ฐ๋์ ํ์คํธ์ผ์ด์ค ์คํจ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ๋ณด๋๋ค. ๊ทธ๋ผ์๋ ์ ๋ ฌ ๋ฌธ์  ๋ณด๋ค๋ ์๊ณ ๋ฆฌ์ฆ์ด ์ต์ํ์ง ์์ ์๊ตญ ์ฌ์ฌ ๋ฌธ์ ๋ฅผ ํ๊ณ ํ๊ณ  ์ถ์ด์ ์ ๋๋ค.

### ๐ ์ด์ง ํ์

#### ์๊ตญ ์ฌ์ฌ

์ถ์ฒ : ํ๋ก๊ทธ๋๋จธ์ค
์๊ตญ ์ฌ์ฌ

๋ด ๋ต์

function solution(n, times) {
times.sort((a, b) => a - b);

let minTime = 0;
let left = 1;
let right = n * Math.max(...times);

while (left <= right) {
let midTime = Math.floor((left + right) / 2);
let peopleCnt = 0;

for (const time of times) {
peopleCnt += Math.floor(midTime / time);
}

if (peopleCnt >= n) {
minTime = midTime;
right = midTime - 1;
} else {
left = midTime + 1;
}
}
return minTime;
}



#### ๐ก๊ตฌํ ๋ฐฉ๋ฒ

์ด์  ์๊ณ ๋ฆฌ์ฆ ํน๊ฐ์์ ์ ํ์ฌํญ์ ๋ณด๋ฉด ๋์ถฉ ์ด๋ค ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์ง์ผํ  ์ง ๋ณด์ธ๋ค๊ณ  ํ์๋ค.
๊ทธ๋์ ์ ํ์ฌํญ์ 1,000,000,000 ์ด๊ฐ ๋๋ฌธ์ ์ด ๋ฌธ์ ๋ ๋ฌด์กฐ๊ฑด ์ด์ง ํ์์ผ๋ก ํธ๋ ๊ฒ์ด๋ผ ํ์ ์ ํ๊ณ  ๊ตฌํํด๋ณด์๋ค.

1. ์ฐ์  ์ด์ง ํ์์ ๋ฐ์ดํฐ๋ค์ด ์ ๋ ฌ ๋์ด ์์ด์ผ ์ฌ์ฉํ  ์ ์๊ธฐ ๋๋ฌธ์ ๋จผ์  times๋ฅผ ์ ๋ ฌํ์๋ค.
2. ์ต์, ์ต๋ ์๊ฐ๋ฅผ ๊ตฌํ ๋ค ๊ตฌํ๋ ค๋ ๋ต์ ์ด์ง ํ์์ผ๋ก ๋ฒ์๋ฅผ ์ขํ ๊ฐ๋ฉฐ ๋ต์ ๊ตฌํ๋ค.
• ์ต์, ์ต๋ ์๊ฐ์ ์ค๊ฐ๊ฐ์ธ midTime๊ฐ n๋ช์ ์ฌ์ฌ ํ  ์ ์๋์ง ์๋์ง๋ฅผ ํ์ํ์๋ค.
3. n๋ช์ ์ฌ์ฌ ํ  ์ ์๋ค๋ฉด minTime์ ๊ฐฑ์ ํ๊ณ  ์ต๋ ๋ฒ์๋ฅผ ์ค์ด๊ณ  n ๋ช์ ์ฌ์ฌํ  ์ ์๋ค๋ฉด ์ต์ ์๊ฐ์ ๋๋ ค์ฃผ๋๋ก ๋ฐ๋ณตํ์๋ค.

๋ชจ๋ฒ ๋ต์

function solution2(n, times) {
const sortedTimes = times.sort((a, b) => a - b);
let left = 1;
let right = sortedTimes[sortedTimes.length - 1] * n;

while (left <= right) {
const mid = Math.floor((left + right) / 2);
const sum = times.reduce((acc, time) => acc + Math.floor(mid / time), 0);

if (sum < n) {
left = mid + 1;
} else {
right = mid - 1;
}
}

return left;
}


### ๐ฅ ๋๋์ 

๋ฌธ์  ์ ํ์กฐ๊ฑด์ ๋ณด๊ณ  ์ ํ ์ฐพ๊ธฐโ๏ธ
์ด์  ์๊ณ ๋ฆฌ์ฆ ํน๊ฐ์์ ๋ฌธ์  ์ ํ ํ์ ๋ฐฉ๋ฒ์์ ์๋์ ๊ฐ์ ๋ถ๋ถ์ ์๊ธฐํด์ฃผ์จ๋ค.

1. ๋ฌธ์  ์ ํ์ ๋ฐ๋ก ํ์ํ๋ ๊ฒ๋ณด๋ค๋ ๊ฐ๋ฅ์ฑ ์๋ ๋ฐฉ๋ฒ์ ์ขํ๋๊ฐ๋ผ
2. ์์ถ๋ ฅ ์ ํ๋ถํฐ ํ์ธ

๊ทธ๋์ ์ค๋ ๋ฌธ์ ๋ฅผ ๋ณผ ๋ 1,000,000,000 ๋ผ๋ ์ ํ๊ณผ ~๋ผ๋ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์ต๋/์ต์ ๊ฐ์ ์ฐพ์๋ผ์ ๋ณด์๋ง์ ๋ฐ๋ก ์ด์ง ํ์์ด ๋ ์ฌ๋๊ณ  "์ ์ด๋ ๊ฒ ์ฐ์๋๋๊น ๋ฐ๋ก ํ ์ ์๊ฒ ๊ตฌ๋" ๋ผ๊ณ  ์๊ฐํ๊ฒ ๋์๋ค.๐

๋ํ ์ ๋ minTime์ ์ ์ธ ํ์ฌ ์ค๊ฐ์ ๊ฐฑ์ ํด์ฃผ์๋๋ฐ left์ right๋ง์ผ๋ก๋ ๊ณ์ฐํ  ์ ์๋ค๋ ๊ฒ์ ์์๋ค. return๊ฐ์ left๋ก ํ๋ฉด ๋๋ ๊ฑฐ์๋๋ฐ.. ์ด๊ฒ ์๊ณ ๋ฆฌ์ฆ์ ์๋ฒฝํ ์ดํดํ์ง ๋ชปํด์ ์๊ธด ๋ณ์๊ฐ ์๋๊น ์ถ์๋ค.๐ฑ
๋ช ์ผ ๋์ ์๊ณ ๋ฆฌ์ฆ์ ํ๊ณ  ์๋๋ฐ ๋ค ์๊ณ ์๋ ์๊ณ ๋ฆฌ์ฆ์์๋ ๋ถ๊ตฌํ๊ณ  ํ์ ๋ ๋ง๊ณ  ํ์ ํ๊ฒ ์ตํ๋ค๋ ์๊ฐ์ด ๊ณ์ ๋ค์๋ค. ์์ผ๋ก ์ง๊ธ์ฒ๋ผ ๊พธ์คํ ๋ธ๋ ฅํด์ผ์ง๐คฏ

### Refer

์ฝ๋ฉํ์คํธ ์ฐ์ต | ํ๋ก๊ทธ๋๋จธ์ค

#### ์ค๋์ ๋ด์ฉ ์ ๋ฆฌ

๋ฐ๋ธ์ฝ์ค Day5

๋งค ์๊ฐ ์ฑ์ฅํ๋ ๊ฐ๋ฐ์๊ฐ ๋๋ ค๊ณ  ๋ธ๋ ฅํ๊ณ  ์์ต๋๋ค.

#### 2๊ฐ์ ๋๊ธ

2022๋ 3์ 25์ผ

์๊ณ ๋ฆฌ์ฆ ํน๊ฐ์์ n ๋ฒ์ ๋ณด๊ณ  ์๊ณ ๋ฆฌ์ฆ ์ ํํ๋ผ๋ ๊ฑฐ ์ง์ง ์ค์  ๊ฟํ์ธ๊ฑฐ ๊ฐ์ต๋๋ค..

1๊ฐ์ ๋ต๊ธ