[백준] 1300번 'K번째 수' - Java

https://www.acmicpc.net/problem/1300

1300번: K번째 수

---

문제

---

코드

import java.io.*;

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		int n = Integer.parseInt(bf.readLine());
		int k = Integer.parseInt(bf.readLine());
		
		long start = 1;
		long end = k;
		
		while(start < end) {
			long mid = (start + end) / 2;
			long cnt = 0;
			
			for(int i = 1 ; i <= n ; i++) {
				cnt += Math.min(mid / i, n);
			}
			
			if(k <= cnt) end = mid;
			else start = mid + 1;
		}
		
		bw.write(start + "\n");
		
		bf.close();
		bw.flush();
		bw.close();
	}
}

 

만약 처음에 k를 이용해서 B[k] = x의 값을 구하는 문제라고 접근하셨다면 저처럼 메모리초과를 겪으셨으리라 생각합니다..

 

이 문제는 x를 움직여서 k의 값에 맞는지 아닌지를 확인하여 x를 맞추는 매개 변수 탐색 문제입니다.

위는 2차원 배열인 A 이고, 밑은 A의 값을 오름차순 배열한 B입니다.

 

k는 k번째로 큰 숫자를 의미합니다. 즉 k보다 작거나 같은 수는 k개라는 말이 됩니다.

 

구구단에서 만약 4보다 작은 값을 찾으라고 했을 때, 1단에서는 4/1 = 4 이므로 4개가, 2단에서는 4/2 = 2 이므로 2개가, 3단에서는 4/3 = 1 이므로 1개가, 4단에서는 4/4 = 1 이므로 1개가 있을 것입니다. 따라서 총 4 + 2 + 1 + 1 = 8 개가 존재합니다. k = 8 이라면 4가 정답이 된다는 말입니다.

만약 k 가 8보다 작거나 같다면 end에 x(mid) 를 넣고, 크다면 start에 x를 넣어 x를 조건에 맞춰가면 됩니다.

---

Search

찾아본 블로그에서 구구단을 예로 들어주셨는데, 이해가 쉽게 되어 좋았습니다.

https://st-lab.tistory.com/281