๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/2805
- ์๊ทผ์ด๋ ๋๋ฌด M๋ฏธํฐ๊ฐ ํ์ํ๋ค.
- ์๊ทผ์ด๋ ์๋ก ๊ตฌ์ ํ ๋ชฉ์ฌ์ ๋จ๊ธฐ๋ฅผ ์ด์ฉํด์ ๋๋ฌด๋ฅผ ๊ตฌํ ๊ฒ์ด๋ค.
- ์๊ทผ์ด๋ ํ๊ฒฝ์ ๋งค์ฐ ๊ด์ฌ์ด ๋ง๊ธฐ ๋๋ฌธ์, ๋๋ฌด๋ฅผ ํ์ํ ๋งํผ๋ง ์ง์ผ๋ก ๊ฐ์ ธ๊ฐ๋ ค๊ณ ํ๋ค.
- ์ด๋, ์ ์ด๋ M๋ฏธํฐ์ ๋๋ฌด๋ฅผ ์ง์ ๊ฐ์ ธ๊ฐ๊ธฐ ์ํด์ ์ ๋จ๊ธฐ์ ์ค์ ํ ์ ์๋ ๋์ด์ ์ต๋๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ๋ชฉ์ฌ์ ๋จ๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ด ๋์ํ๋ค. ๋จผ์ , ์๊ทผ์ด๋ ์ ๋จ๊ธฐ์ ๋์ด H๋ฅผ ์ง์ ํด์ผ ํ๋ค.
- ๋์ด๋ฅผ ์ง์ ํ๋ฉด ํฑ๋ ์ด ๋ ์ผ๋ก๋ถํฐ H๋ฏธํฐ ์๋ก ์ฌ๋ผ๊ฐ๋ค.
- ๊ทธ ๋ค์, ํ ์ค์ ์ฐ์ํด์๋ ๋๋ฌด๋ฅผ ๋ชจ๋ ์ ๋จํด๋ฒ๋ฆฐ๋ค.
- ๋ฐ๋ผ์, ๋์ด๊ฐ H๋ณด๋ค ํฐ ๋๋ฌด๋ H ์์ ๋ถ๋ถ์ด ์๋ฆด ๊ฒ์ด๊ณ , ๋ฎ์ ๋๋ฌด๋ ์๋ฆฌ์ง ์์ ๊ฒ์ด๋ค.
- ์๋ฅผ ๋ค์ด, ํ ์ค์ ์ฐ์ํด์๋ ๋๋ฌด์ ๋์ด๊ฐ 20, 15, 10, 17์ด๋ผ๊ณ ํ์.
- ์๊ทผ์ด๊ฐ ๋์ด๋ฅผ 15๋ก ์ง์ ํ๋ค๋ฉด, ๋๋ฌด๋ฅผ ์๋ฅธ ๋ค์ ๋์ด๋ 15, 15, 10, 15๊ฐ ๋ ๊ฒ์ด๊ณ , ์๊ทผ์ด๋ ๊ธธ์ด๊ฐ 5์ธ ๋๋ฌด์ 2์ธ ๋๋ฌด๋ฅผ ๋ค๊ณ ์ง์ ๊ฐ ๊ฒ์ด๋ค. (์ด 7๋ฏธํฐ๋ฅผ ์ง์ ๋ค๊ณ ๊ฐ๋ค)
- ์ ๋จ๊ธฐ์ ์ค์ ํ ์ ์๋ ๋์ด๋ ์์ ์ ์ ๋๋ 0์ด๋ค.
- ์ฒซ์งธ ์ค์ ๋๋ฌด์ ์ N๊ณผ ์๊ทผ์ด๊ฐ ์ง์ผ๋ก ๊ฐ์ ธ๊ฐ๋ ค๊ณ ํ๋ ๋๋ฌด์ ๊ธธ์ด M์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
- ๋์งธ ์ค์๋ ๋๋ฌด์ ๋์ด๊ฐ ์ฃผ์ด์ง๋ค. ๋๋ฌด์ ๋์ด์ ํฉ์ ํญ์ M๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ธฐ ๋๋ฌธ์, ์๊ทผ์ด๋ ์ง์ ํ์ํ ๋๋ฌด๋ฅผ ํญ์ ๊ฐ์ ธ๊ฐ ์ ์๋ค.
- ๋์ด๋ 1,000,000,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ ์ ์ ๋๋ 0์ด๋ค.
- ์ ์ด๋ M๋ฏธํฐ์ ๋๋ฌด๋ฅผ ์ง์ ๊ฐ์ ธ๊ฐ๊ธฐ ์ํด์ ์ ๋จ๊ธฐ์ ์ค์ ํ ์ ์๋ ๋์ด์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ์ด๋ถํ์์ ์ด์ฉํ์ฌ ๋ฌธ์ ๋ฅผ ํ์ด์ผ๊ฒ ๋ค๊ณ ์๊ฐํ๋ค.
- ๋ฐ๋ผ์ ์ ๋ ฅ๋ฐ์ผ๋ฉด์ ๋๋ฌด ๊ธธ์ด์ค ์ต๋๊ฐ์ ์ฐพ์์ ์ต์๊ฐ 0์ ์์์ ์ผ๋ก, ์ต๋๊ฐ์ ๋์ ์ผ๋ก ์ก์์ ์ด๋ถํ์์ ๋๋ ธ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ2805 {
static int N;
static int M;
static int max;
static int trees[];
static long result;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// ๋๋ฌด์ ์
N = Integer.parseInt(st.nextToken());
// ํ์ํ ๋๋ฌด์ ๊ธธ์ด
M = Integer.parseInt(st.nextToken());
// ์ต๋๊ฐ
max = Integer.MIN_VALUE;
trees = new int[N];
// ๋์ด ์ต๋๊ฐ ๊ฒฐ๊ณผ
result = 0;
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){
int n = Integer.parseInt(st2.nextToken());
// ์ต๋๊ฐ ๊ฐฑ์
if(n > max){
max = n;
}
// ๋๋ฌด ๊ธธ์ด ๋ฐฐ์ด์ ์ ์ฅ
trees[i] = n;
}
DFS(0, max);
System.out.println(result);
}
public static void DFS(long s, long f){
// ์์ ๊ธธ์ด๊ฐ ๋ ๊ธธ์ด๋ณด๋ค ๊ธธ์ด์ง๋ฉด ์ข
๋ฃ
if(s > f){
return;
}
// ๋๋ฌด ๊ฐ์ ์นด์ดํธ ๋ณ์
long cnt = 0;
// ์๋ฅผ ๋๋ฌด ๊ธธ์ด
// ๊ธธ์ด๋ฅผ ์์์ ๊ณผ ๋์ ์ ์ค๊ฐ์ง์ ์ผ๋ก ์ค์
long len = (f + s)/2;
for(int i = 0; i < N; i++){
// ๋๋ฌด๋ฅผ ์๋ฅด๊ณ ๋จ์ ๊ธธ์ด๋ฅผ ์ ์ฅํ ๋ณ์
long minus = 0;
// ๋ฐฐ์ด์ ์ ์ฅ๋์ด์๋ ๋๋ฌด๊ธธ์ด์ ์๋ฅผ ๋๋ฌด๊ธธ์ด๋ฅผ ๋นผ์ค
minus = trees[i] - len;
// ๋ง์ฝ ๋บ ๊ธธ์ด๊ฐ ์์๋ผ๋ฉด ํด๋น ๋๋ฌด๋ ํด๋น ๊ธธ์ด๋ก ์๋ฅผ ์ ์๋ค๋
// ๋ป์ด๋ฏ๋ก 0์ผ๋ก ๋ค์ ์ ์ฅ
if(minus < 0){
minus = 0;
}
// ์ ์ฒด ๋จ์ ๋๋ฌด ๊ธธ์ด์ ํด๋น ๋จ์ ๋๋ฌด ๊ธธ์ด๋ฅผ ์ ์ฅ
cnt = cnt + minus;
}
// ๋ง์ฝ ๋จ์ ๋๋ฌด ๊ธธ์ด๊ฐ ํ์ํ ๋๋ฌด ๊ธธ์ด๋ณด๋ค ๊ฐ๊ฑฐ๋ ํฌ๋ค๋ฉด
// ์๋ฅด๋ ๋๋ฌด ๊ธธ์ด๋ฅผ ๋ ๊ธธ๊ฒ ํด๋ ๋๋ค๋ ๋ป์ด๋ฏ๋ก
if(cnt >= M){
// ๊ฒฐ๊ณผ๊ฐ์ ํ์ฌ ๋๋ฌด ๊ธธ์ด๋ก ์ ์ฅํด์ฃผ๊ณ
result = len;
// ์์ ์ง์ ์ ์ค๊ฐ ๊ธธ์ด + 1๋ก ์ค์
DFS(len + 1, f);
}
// ๋ง์ฝ ๋จ์ ๋๋ฌด ๊ธธ์ด๊ฐ ํ์ํ ๋๋ฌด ๊ธธ์ด๋ณด๋ค ์์ผ๋ฉด
// ์๋ฅด๋ ๋๋ฌด ๊ธธ์ด๊ฐ ๋ ์งง์์ผ๋๋ฏ๋ก
else if(cnt < M){
// ๋ ์ง์ ์ ์ค๊ฐ ๊ธธ์ด - 1๋ก ์ค์
DFS(s, len - 1);
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 18111 ๋ง์ธํฌ๋ํํธ (0) | 2024.08.14 |
---|---|
[Java] BOJ 11724 ์ฐ๊ฒฐ ์์์ ๊ฐ์ (0) | 2024.08.13 |
[Java] BOJ 11279 ์ต๋ ํ (0) | 2024.08.11 |
[Java] BOJ 2630 ์์ข ์ด ๋ง๋ค๊ธฐ (0) | 2024.08.05 |
[Java] BOJ 1541 ์์ด๋ฒ๋ฆฐ ๊ดํธ (0) | 2024.08.02 |