- golang
- C++
- go
- ์ฌ๊ท
- nestjs
- ์ฌ๋ผ์ด๋ฉ ์๋์ฐ
- Union-Find
- ๋ฐฑ์๋ ํ๋ฆฌ์จ๋ณด๋ฉ
- ์๊ณ ๋ฆฌ์ฆ
- ํ๋ก๊ทธ๋๋จธ์ค
- ์นด์นด์ค2021
- ๋ค์ต์คํธ๋ผ
- ์นด์นด์ค ์ฝํ
- BFS
- ํ๋ฆฌ์จ๋ณด๋ฉ
- Python
- js
- ๋นํธ๋งต
- ํธ๋ฆฌ
- ์ด๋ถํ์
- ๋์ ํ๋ก๊ทธ๋๋ฐ
- DFS
- DP
- ์น๋ฆฐ์ด
- ๋ฐฑ์ค
- ์ํฐ๋
- LCs
- ๋นํธ๋ง์คํน
- ์์ฝ๋
- ๊ฐ์ฅ๊ฐ๊น์ด๊ณตํต์กฐ์
- Today
- Total
Hello Ocean! ๐ผ
[ํ๋ก๊ทธ๋๋จธ์ค] ์ ๊ตญ ์ฌ์ฌ ๋ณธ๋ฌธ
๋ฌธ์ ์ค๋ช
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์ฌ์ฌ์๊ฐ
- ์ต๋๊ฐ์ ์ด๋ป๊ฒ ๊ตฌํด์ผ ํ๋๊ฐ?


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
'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ํ๊ฒ ๋๋ฒ, C++ (0) | 2020.09.21 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] ์์ฅ (0) | 2020.09.14 |
[ํ๋ก๊ทธ๋๋จธ์ค] ์์ฃผํ์ง ๋ชปํ ์ ์ (0) | 2020.09.07 |
[์๊ณ ๋ฆฌ์ฆ] ์ต๋ ์ต์ ์ฐพ๊ธฐ (ํ ๋๋จผํธ ํธ๋ฆฌ) (0) | 2020.09.07 |
[์๊ณ ๋ฆฌ์ฆ] ํ์ ์๊ณ ๋ฆฌ์ฆ (์ ํ, ์ด๋ถ, ํด์, BST) (0) | 2020.08.31 |