๐ ๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/22254
โธ ๋ฌธ์
๊ฑฐ๋ญ๋ ์ฐฝ์ ์ฑ๊ณต์ ์ด๋ฃฌ ๋ฅ์ง๊ตญ ์ฌ์ฅ์ ์ด๋ฒ์๋ ๋ง์ถคํ ์ ๋ฌผ์ ์ ์ํด์ฃผ๋ ๊ณต์ฅ์ ๋ง๋ค๊ธฐ๋ก ํ๋ค. ํ์ฌ ๋ค์ด์จ ๋ง์ถคํ ์ ๋ฌผ ์ฃผ๋ฌธ์ ์ด N๊ฐ์ด๋ฉฐ, ๊ฐ ๋ง์ถคํ ์ ๋ฌผ๋ง๋ค ์ ์์ ํ์ํ ์๊ฐ์ด ์ ํด์ ธ์๋ค. ์ฃผ๋ฌธ์ ๋ฒํธ๋ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง ๋งค๊ฒจ์ ธ ์์ผ๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ ๋ง๊ฒ ๊ณต์ ์ด ์ด๋ค์ง๋ค.
- ๊ณต์ ๋ผ์ธ์ด ์ด K๊ฐ๊ฐ ์๋ค๋ฉด 1๋ฒ๋ถํฐ K๋ฒ๊น์ง์ ๋ฒํธ๊ฐ ์กด์ฌํ๋ค.
- ๊ณต์ ๋ผ์ธ์ ์ฌ์ฉ ์๊ฐ์ ๋ฐฐ์ ๋ ๋ง์ถคํ ์ ๋ฌผ๋ค์ ์ ์ ์๊ฐ์ ์ดํฉ์ด๋ค.
- โi๋ฒ ์ ๋ฌผ์ 1๋ฒ ๋ถํฐ i−1๋ฒ ์ ๋ฌผ๋ค์ด ๋ฐฐ์ ๋ ์ดํ์ ์ฌ์ฉ ์๊ฐ์ด ๊ฐ์ฅ ์ ์ ๊ณต์ ๋ผ์ธ ์ค ํ๋์ ๋ฐฐ์ ๋๋ค.
๋ชจ๋ ๋ง์ถคํ ์ ๋ฌผ์ ์ ์์ด ์๋ฃ๋ ๋๊น์ง ์ต๋ X์๊ฐ์ด ๋จ์์๋ ์ํฉ์ธ๋ฐ, ์์ง ๊ณต์ ๋ผ์ธ์ ๊ฐ์ K๊ฐ ์ ํด์ ธ ์์ง ์๋ค. ๋ฅ์ง๊ตญ ์ฌ์ฅ์ ์ด ๋ถ์ผ ์ต๊ณ ๊ถ์์, ๊ณต์ ์ปจ์คํดํธ ํธ์์๊ฒ ์๋ขฐํ๋ค. ๊ณต์ ์ปจ์คํดํธ ํธ์์ ์ต์ํ์ ๋น์ฉ์ ์ฐ๊ธฐ ์ํด์ ๊ณต์ ๋ผ์ธ์ ๊ฐ์๋ฅผ ์ต์ํ ์ํค๊ณ ์ ํ๋ค. ํธ์์ ๋์ ํ์ํ ์ต์ ๊ณต์ ๋ผ์ธ ๊ฐ์๋ฅผ ๊ณ์ฐํ์.
โธ ์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์ ๋ง์ถคํ ์ ๋ฌผ ์ฃผ๋ฌธ์ ๊ฐ์ N, ์ ์ ์๋ฃ๊น์ง ๋จ์ ์๊ฐ X๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค.
๋ ๋ฒ์งธ ์ค์๋ 1๋ฒ๋ถํฐ N๋ฒ ์ ๋ฌผ์ด ํ์ํ ๊ณต์ ์๊ฐ์ด ์์๋๋ก ์ฃผ์ด์ง๋ค. ๋จ์๋ '์๊ฐ' ์ด๋ค.
โธ ์ถ๋ ฅ
๋ชจ๋ ์ ๋ฌผ์ X์๊ฐ ์ด๋ด์ ์ ์ํ๊ธฐ ์ํด ํ์ํ ์ต์ ๊ณต์ ๋ผ์ธ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ผ.
โธ ์ ํ
- 1≤N≤100,000, N์ ์์ฐ์์ด๋ค.
- โ1≤X≤10 ^9, X๋ ์์ฐ์์ด๋ค.
- โ1≤ ๊ฐ ์ ๋ฌผ์ ๊ณต์ ์๊ฐ ≤X, ๋ชจ๋ ์๊ฐ์ ์์ฐ์์ด๋ค.
๐ ๋ฌธ์ ์ ๋ณด
- ๐ฅ ๋ฌธ์ ๋ ๋ฒจ : ๊ณจ๋ 3
- ๐ ๋ฌธ์ ์ ํ : ์๋ฃ ๊ตฌ์กฐ, ์ด๋ถ ํ์, ์ฐ์ ์์ ํ, ๋งค๊ฐ ๋ณ์ ํ์
- ๐ฌ ํ์ด ์ธ์ด : JAVA
๐ค ๋ฌธ์ ํ์ด
๊ฐ ์ ๋ฌผ๋ง๋ค ์ ์์ ํ์ํ ์๊ฐ์ด ์ ํด์ ธ ์์ ๋,
์ต๋ x์๊ฐ ์ด๋ด์ ๋ชจ๋ ์ ๋ฌผ์ ์ ์ํ๊ธฐ ์ํด ํ์ํ ์ต์ ๊ณต์ ๋ผ์ธ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค.
์ด ๋ฌธ์ ๋ ์ด๋ถ ํ์๊ณผ ์ฐ์ ์์ ํ๋ฅผ ํ์ฉํ์ฌ ํด๊ฒฐํ ์ ์๋ค.
๐น ๊ณต์ ๋ผ์ธ์ ๊ฐ์๋ฅผ ๊ธฐ์ค์ผ๋ก ์ด๋ถ ํ์์ ์งํํ๋ค.
๊ณต์ ๋ผ์ธ์ ์ต์ ๊ฐ์๋ 1๊ฐ, ์ต๋ ๊ฐ์๋ ์ ๋ฌผ์ ๊ฐ์์ธ n๊ฐ๋ค.
mid๊ฐ์ ๊ณต์ ๋ผ์ธ์ผ๋ก x์๊ฐ ์ด๋ด์ ์ ์์ด ๊ฐ๋ฅํ๋ฉด, ๋ ์์ ๊ฐ์๋ก๋ ๊ฐ๋ฅํ์ง ํ์ธํ๋ค.
๋ถ๊ฐ๋ฅํ๋ค๋ฉด, ๊ณต์ ๋ผ์ธ ๊ฐ์๋ฅผ ๋๋ ค์ผ ํ๋ฏ๋ก ๋ ํฐ ๋ฒ์๋ฅผ ํ์ํ๋ค.
๐น mid๊ฐ์ ๊ณต์ ๋ผ์ธ์์ ์ ๋ฌผ์ ๋ฐฐ์ ํ๋ ๋ฐฉ์์ผ๋ก ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋ค.
ํ์ฌ๊น์ง ์ฌ์ฉ๋ ๊ณต์ ์๊ฐ์ด ๊ฐ์ฅ ์ ์ ๋ผ์ธ์ ์๋ก์ด ์ ๋ฌผ์ ๋ฐฐ์ ํ๋ค.
์ ๋ฌผ์ ๋ฐฐ์ ํ๋ฉด์ ์ด ์๊ฐ์ด x๋ฅผ ์ด๊ณผํ๋ฉด false๋ฅผ ๋ฐํํด mid๋ฅผ ์ฆ๊ฐ์์ผ ํ์ํ๋๋ก ํ๋ค.
์ ํ์ด๋ฅผ ์ฝ๋๋ก ์์ฑํด ๋ณด๋ฉด ์๋์ ๊ฐ๋ค.
โ ์ต์ข ์ฝ๋
๋ฉ๋ชจ๋ฆฌ : 77216KB
์๊ฐ : 868ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int n, x;
static int[] ProcessTime;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // ์ ๋ฌผ ์ฃผ๋ฌธ ๊ฐ์
x = Integer.parseInt(st.nextToken()); // ์ ์ ์๋ฃ๊น์ง ๋จ์ ์๊ฐ
ProcessTime = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
ProcessTime[i] = Integer.parseInt(st.nextToken());
}
int start = 1;
int end = n;
while (start <= end) {
int mid = start + (end-start) / 2; // ๊ณต์ ๋ผ์ธ ๊ฐ์
if (isPossible(mid)) { // ํ์ฌ ๊ณต์ ๋ผ์ธ ๊ฐ์๋ก ์๊ฐ์ ๋ง์ถฐ ์ ์์ ๋๋ผ ์ ์๋ค๋ฉด
end = mid-1;
} else start = mid+1;
}
System.out.println(start);
}
private static boolean isPossible(int mid) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < mid; i++) { // ๊ณต์ ๋ผ์ธ ๊ฐ์๋งํผ 0(์๊ฐ)์ผ๋ก ์ฑ์ฐ๊ธฐ
pq.offer(0);
}
for (int i = 0; i < n; i++) {
int nowTime = pq.poll();
// ์๊ฐ ์์ ๋๋ด์ง ๋ชปํจ
if (nowTime+ProcessTime[i] > x) return false;
pq.offer(nowTime+ProcessTime[i]);
}
return true;
}
}
๊ณจ๋ 3 ๋ฌธ์ ์ธ๋ฐ ์๊ฐ๋ณด๋ค ์ด๋ ต์ง ์๊ฒ ํ์๋ค. ์ด๋ถ ํ์ ๋ฌธ์ ์ ๊ฐ์ด ์กํ๊ฐ๋ ๊ฒ ๊ฐ์์ ๋ฟ๋ฏํ๋ค. ๐
์ฐ์ ์์ ํ๋ก ํด๊ฒฐํ๋ ๋ถ๋ถ์ ์ด ๋ฌธ์ ์ ์ ์ฌํ๋ ๊ฒ ๊ฐ๋ค.
ํด๊ฒฐ ์๋ฃ ! ๐ฅ
'Algorithm > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Boj_2696] ์ค์๊ฐ ๊ตฌํ๊ธฐ (0) | 2025.02.15 |
---|---|
[Boj_12014] ์ฃผ์, LIS (0) | 2025.02.11 |
[Boj_5214] ํ์น (0) | 2025.01.31 |
[Boj_16509] ์ฅ๊ตฐ (0) | 2025.01.30 |
[Boj_1854] K๋ฒ์งธ ์ต๋จ๊ฒฝ๋ก ์ฐพ๊ธฐ (0) | 2025.01.25 |