์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
- dfs
- ํฌํฌ์ธํฐ
- ํธ๋ผ์ด
- ํ๋ก์ด๋์์
- Union Find
- ์๋ฃ๊ตฌ์กฐ
- ๊ทธ๋ฆฌ๋
- ๋นํธ๋ง์คํน
- ์นด์นด์ค
- ์กฐํฉ
- ํ์๊ฐ์
- ์ธ๊ทธ๋จผํธํธ๋ฆฌ
- ์ด๋ถํ์
- LowerBound
- ๋ฐฑํธ๋ํน
- ์๋ฎฌ๋ ์ด์
- ๋ค์ต์คํธ๋ผ
- dp
- Dijkstra
- upperbound
- ์์ด
- ์ฐ์ ์์ํ
- ์ด์งํธ๋ฆฌ
- Floyd
- ๋ถ๋ถ์งํฉ
- ์ฌ๊ท
- Django
- BFS
- PriorityQueue
- ๊ตฌํ
- Today
- Total
J
[JAVA] BOJ ๋ฐฑ์ค 1654 ๋์ ์๋ฅด๊ธฐ ๋ณธ๋ฌธ
[JAVA] BOJ ๋ฐฑ์ค 1654 ๋์ ์๋ฅด๊ธฐ
snowball๐ฐ 2023. 2. 27. 15:37https://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๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ ์ฒด ์ฝ๋
import java.util.*;
import java.io.*;
public class Main {
static long[] lan;
static int K, N;
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
lan = new long[K];
long max = 0;
for(int i=0; i<K; i++) {
lan[i] = Integer.parseInt(bf.readLine());
max = Math.max(max, lan[i]);
}
find(0, max);
}
static void find(long start, long end) {
long min = start; long max = end;
while(min <= max) {
long mid = (min+max) / 2;
if(cut(mid)) min = mid+1;
else max = mid -1;
}
System.out.println(min-1);
}
static boolean cut(long h) {
if(h == 0) return true;
long count = 0;
for(int i=0; i<K; i++)
count += (lan[i] / h);
if(count >= N) return true;
else return false;
}
}
๐ก ์ด๋ถํ์์์ ์ค์ํ ๋ถ๋ถ์ while์ ์กฐ๊ฑด๊ณผ start, end์ ๊ฐฑ์ ๊ณผ ๊ฐฑ์ ์กฐ๊ฑด์ด๋ค.
์ด ๋ฌธ์ ์์ ์ ๋ต์ด ๋ ๊ธธ์ด๋ ๋์ ๊ฐ์๋ฅผ N๋ก ๋ง๋๋ ๊ธธ์ด์ด์ด๋ค.
๊ทธ๋ ๊ธฐ ๋๋ฌธ์ ์กฐ๊ฑด์ ๊ฐ์๊ฐ N๋ณด๋ค (์๊ฑฐ๋) (ํฐ๊ฑฐ๋ ๊ฐ์) ๋ ๊ฒฝ์ฐ๋ก ๋ถ๋ฆฌํด์ผ ํ๋ค.
while์ ์กฐ๊ฑด์ min ≤ max๋ก ์ค์ ํ๊ธฐ ๋๋ฌธ์ while์ด ์ข ๋ฃ๋๋ฉด min = max+1์ ํํ๊ฐ ๋๋ค.
์ ๋ต์ด ๋๋ mid๋ else ์กฐ๊ฑด์ ์ํด mid-1์ด ๋๊ธฐ ๋๋ฌธ์ ๊ฒฐ๊ตญ ๊ฒฐ๊ณผ๊ฐ์ max๋ min-1์ ์ถ๋ ฅํด์ผ ๋๋ค.
while(min < max)์ธ ๊ฒฝ์ฐ๋ ๋ ๊ฐ์ด ๊ฐ์ ๊ฒฝ์ฐ while์ ๋น ์ ธ๋์ค๋๋ฐ ์ด ๊ฒฝ์ฐ ๋ฌดํ loop๋ฅผ ๋๋ ๊ฒฝ์ฐ๊ฐ ์๊ธฐ๊ฒ ๋๋ค.
์ด๋ h๊ฐ 0์ธ ๊ฒฝ์ฐ๋ฅผ ์ฃผ๋ชฉํ์ ! ๋์ ์ ๊ธธ์ด๊ฐ 1์ด ์ต๋์ธ ๊ฒฝ์ฐ ์ฐ๋ฆฌ๋ h๊ฐ 0์ผ๋ก ์กฐ์ฌ๋ฅผ ํ๊ฒ ๋๋ค. ๋๋ฌธ์ 0์ด ๋ค์ด์ค๋ฉด true๋ฅผ ์ฃผ์!(์ค์ ๋ก๋ 0์ด ๋ต์ด ์๋๋ฏ๋ก false๋ก ๋๊ปด์ง์ ์๋ค. ํ์ง๋ง true, false๋ฅผ ๊ฐ๋ฅํ ๋ต์ด ์๋ mid์ ์ฆ๊ฐ์ผ๋ก ๊ณ ๋ คํด์ผ ํ๋ค.)
'๐ Problem Solving > ๐ BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[JAVA] BOJ ๋ฐฑ์ค 16724 ํผ๋ฆฌ ๋ถ๋ ์ฌ๋์ด (0) | 2023.03.29 |
---|---|
[JAVA] BOJ ๋ฐฑ์ค 4811 ์์ฝ (0) | 2023.03.28 |
[JAVA] BOJ ๋ฐฑ์ค 2110 ๊ณต์ ๊ธฐ ์ค์น (0) | 2023.02.27 |
[JAVA] BOJ ๋ฐฑ์ค 2343 ๊ธฐํ ๋ ์จ (0) | 2023.02.27 |
[JAVA] BOJ ๋ฐฑ์ค 2805 ๋๋ฌด์๋ฅด๊ธฐ (0) | 2023.02.27 |