J

[JAVA] BOJ ๋ฐฑ์ค€ 1654 ๋žœ์„  ์ž๋ฅด๊ธฐ ๋ณธ๋ฌธ

๐Ÿ”‘ Problem Solving/๐Ÿ‡ BOJ

[JAVA] BOJ ๋ฐฑ์ค€ 1654 ๋žœ์„  ์ž๋ฅด๊ธฐ

snowball๐Ÿฐ 2023. 2. 27. 15:37

https://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์˜ ์ฆ๊ฐ์œผ๋กœ ๊ณ ๋ คํ•ด์•ผ ํ•œ๋‹ค.)

 

Comments