ํฐ์คํ ๋ฆฌ ๋ทฐ
https://www.acmicpc.net/problem/2805
์ด ๊ธ์ ์ด๋ถํ์์ ์ด๋ฏธ ์๊ณ ์๋ ์ฌ๋์ ๋์์ผ๋ก ์์ฑํ๋ค.
- ์ด๋ถํ์์ ์ด์ฉํด ์ต์ ์ ๊ฐ์ ์ฐพ์๋ธ๋ค.
- ์ด๋ถํ์ ๋ฌธ์ ์์๋ ๊ตฌํด์ผํ๋ ๊ฐ์ ์ฐพ๊ณ ํด๋น ๊ฐ์ ๊ธฐ์ค์ผ๋ก ํ์ดํ๋ค. ๋ณดํต ์ ๋ต์ ์๊ตฌํ๋ ๊ฐ๊ณผ ์ผ์นํ๋ค.
- ํด๋น ๋ฌธ์ ์์๋ K(์ ๋จ๊ธฐ์ ์ค์ ํ ๋์ด์ ์ต๋๊ฐ)์ด ๊ธฐ์ค ๊ฐ์ด๋ค.
- ๋ฐ๋ผ์ ๋ณํํ๋ K๋ฅผ ๊ธฐ์ค์ผ๋ก totalSlicedHeight(์๋ ค์ง ๋๋ฌด ๊ธธ์ด์ ํฉ)์ด M(๊ฐ์ ธ๊ฐ์ผํ ๋๋ฌด ๊ธธ์ด)๋ณด๋ค ๋ถ์กฑํ ๋๋ K๋ฅผ ๊ฐ์์ํค๊ณ
- totalSlicedHeight๊ฐ M๋ณด๋ค ํด ๋๋ K๋ฅผ ์ฆ๊ฐ์ํจ๋ค.
- K์ ๋ํ ์ด๋ถํ์์ด ์ข ๋ฃ๋๋ฉด ํ์๋ K๊ฐ์ ์ถ๋ ฅํ๋ค. ์ด๋ถํ์์ด ์ข ๋ฃ๋๋ ์กฐ๊ฑด์ start > end ์ด๋ค.
์ฝ๋
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class ๋๋ฌด_์๋ฅด๊ธฐ_2805 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int M = Integer.parseInt(input[1]);
List<Integer> woodList = new ArrayList<>();
int maxHeight = 0;
for (String wood : br.readLine().split(" ")) {
int woodHeight = Integer.parseInt(wood);
woodList.add(woodHeight);
maxHeight = Math.max(maxHeight, woodHeight);
}
long start = 0;
long end = maxHeight;
while (start <= end) {
long mid = (start + end) / 2;
long totalSlicedHeight = 0;
for (Integer woodHeight : woodList) {
long slice = woodHeight - mid;
if (slice > 0) {
totalSlicedHeight += slice;
}
}
if (totalSlicedHeight < M) {
end = mid - 1;
} else {
start = mid + 1;
}
}
bw.write(Long.toString(end));
bw.close();
br.close();
}
}
๋ฐ์ํ
'PS > ๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 7576 : ํ ๋งํ - java [์๋ฐ] (0) | 2022.03.02 |
---|---|
[๋ฐฑ์ค] 2667 : ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ - java [์๋ฐ] (0) | 2022.02.28 |
[๋ฐฑ์ค] 11724 : ์ฐ๊ฒฐ ์์์ ๊ฐ์ - java [์๋ฐ] (0) | 2022.02.28 |
[๋ฐฑ์ค] 2252 : ์ค ์ธ์ฐ๊ธฐ - java [์๋ฐ] (0) | 2022.02.27 |
๊ณต์ง์ฌํญ
์ต๊ทผ์ ์ฌ๋ผ์จ ๊ธ
์ต๊ทผ์ ๋ฌ๋ฆฐ ๋๊ธ
- Total
- Today
- Yesterday
TAG
- ํ๋ก๊ทธ๋๋จธ์ค
- ๋ฐฑ์ค
- ์๊ณ ๋ฆฌ์ฆ
- Golang
- ํธ๋์ญ์ ๊ฒฉ๋ฆฌ ์์ค
- mysql ์คํ ๊ณํ
- ๊น์ด/๋๋น ์ฐ์ ํ์(DFS/BFS)
- ์ข์ ์ฝ๋๋ ๋ฌด์์ธ๊ฐ?
- ํด์
- ์คํ/ํ
- ์ข์ ๊ฐ๋ฐ์ ๋๊ธฐ
- 2023 ๊ฐ๋ฐ์ ํ๊ณ
- Aws Reinvent 2023
- ์ฝ๋ฉํ ์คํธ
- ์ถ์ ์ง๋
- mysql
- kotlin s3 upload
- 2023 ํ๊ณ
- ํ(Heap)
- ์ข์ ์์ง๋์ด
- ๋ฑ ํฌ์๋ฌ๋ ๊ฐ๋ฐ์
- ์ฅ์ ํ๊ณ
- AWS re:Invent 2023
- Go
- ์ข์ ๊ฐ๋ฐ์
- golang oomkilled
- grpc client
- rate limit
- HTTP
- 2๋ ์ฐจ ์๋ฒ ๊ฐ๋ฐ์
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |
๊ธ ๋ณด๊ดํจ