백준_1300_K번째 수

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

1300번: K번째 수

해결 방법(초기)

> 문제를 읽고 나서 처음으로 든 생각은 이차원 배열을 선언하고 해당 값으로 초기화한다. 그 후 sum(array,[])을 통하여 1차원으로 만든 후 정렬을 통해 문제를 풀려고 했다.

> 위 방법으로 푼 결과는 다음과 같다.

 

메모리 초과 이유

	Int	4Byte
	1KB	1024Byte
	1MB	1024KB
	128MB	128*1024KB = 33554432개(Int)
문제 조건(입력)	10^5(2차원 배열)	10^10 > 128MB

> 그러므로 2차원 배열이든 쭉 늘여놓은 1차원 배열이든 메모리 초과가 날 수 밖에 없다.

 

해결 방법(결론)

> 문제에서 도출해내야 하는 정답은 K번째 있는 수를 출력하는것이다.

> 그러므로 N*N 배열을 전체 탐색하지 않아도 된다.

> left = 1, right = K로 놓는다. right를 K로 놓아도 이유는 아래에서 설명할 것이다.

> 예를 들어 N이 5, K가 7이라고 가정.

1	2	3	4	5
2	4	6	8	10
3	6	9	12	15
4	8	12	16	20
5	10	15	20	25

위의 2차원 배열을 1차원으로 정렬해서 나열한다면 다음과 같이 나올 것이다.

1 2 2 3 3 4 4 4 .....

right가 K, 즉 7이라고 놓았는데 위에서 보이듯이 중복해서 들어오는 숫자가 존재하므로 K번째 수는 K보다 반드시 작다.

(증명은 어떻게 하는거지....)