[1300] k번째 수 (이분탐색, 2차원 배열)
·
Coding Test/Search
1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 분석 n=3, k=7로 가정 중앙값보다 작거나 같은 수의 개수 = 중앙값을 N으로 나눈 값 1. 최초의 중앙값 : 4 = (1+7)/2 1*1 = 1 1*2 = 2 1*3 = 3 1행 : 4/1 = 4지만 행의 크기가 3개이므로 3 2*1 = 2 2*2 = 4 2*3 = 6 2행 : 4/2 = 2 3*1 = 3 3*2 = 6 3*3 = 9 3행 : 4/3 = 1 cnt를 다 더하면 5이므로 k(7)보다 작음 => 중앙값을 증가시킴 ..