백준 1300번 자바 ☆

문제

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

1300번: K번째 수

1. 시간복잡도와 공간복잡도

시간복잡도 : 해당 문제에서 N의 최대 값이 100,000이다. 시간 복잡도의 경우 2초의 시간이 주어지는데, 약 2억번의 연산이 가능한 시간이다. 그러므로 O(N2)의 시간복잡도를 가지는 알고리즘을 쓰면 시간초과이다.

 

공간복잡도 : 배열A는 2차원 배열로 N*N의 크기를 갖고 배열B의 길이는 N*N이다.

int형 배열을 만든다고 가정했을 때 원소하나의 크기는 4byte이고, N*N = 약 100억

100억 * 4byte = 40,000mb로 문제의 조건에 부적합하다.

 

그러므로 해당 문제는 배열 A,B를 생성하지 않으면서 시간복잡도가 O(NlogN)인 알고리즘을 사용해야한다.

 

2. 접근 방식

해당 문제의 핵심은 '2차원 배열에서 k번째 수는 값 k를 넘지 않는다' 이다. 이 말이 가능한 이유는 배열에 들어가는 값이 순차적으로 증가하는 값이기 때문이다.

 

그렇기 때문에 이분탐색을 할 때 처음시작하는 마지막 값이 k가 된다.

 

두번째로 중요한 핵심은 아래와 같다.

해당 문제 조건에서 2차원 배열의 경우 아래 행으로 내려가면서 n의 배수를 오른쪽 열에 표시를 하게 된다.

1	2	3	4
2	4	6	8
3	6	9	12
4	8	12	16

그렇기 때문에 특정 값 X를 n으로 나누어주면 해당 열안에 X이하의 값이 몇개가 있는지 파악할 수 있다.

예를 들어 X == 7 

첫번째 행 7/1 = 4(단, 여기서 중요한 점은 해당 배열이 4열까지이기 때문에 열의 길이 또는 나누기의 몫 중 더 작은 값이어야한다.)

두번째 행 7/2 = 3

세번째 행 7/3 = 2

네번째 행 7/4 = 1

 

그러므로 위 2차원 배열에서 7이하의 값은 총 10개가 된다.

 

이분탐색을 통해 해당 값을 탐색하면 정답이 도출된다.

 

3. 구현

import java.io.*;
import java.util.*;

public class Main1300 {
	static int N,k;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.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 (cnt < k) {
				start = mid + 1;
				continue;
			} 
			end = mid - 1;
		}
		System.out.println(start);
	}
}

 

정리 : 확실히 골드수준의 문제는 개념을 단순히 이해하는 것을 넘어서 수학적 사고력이 필요한것 같다. 임의의 수를 나눔으로써 몇개가 있는지 파악하는 점은 정말 이런식으로 배우지 않고선 쉽게 생각해내지 못했을 것이다. 하지만 또 하나 배웠으니 다음엔 더 잘풀도록 해보자.