[백준 1300 C++] K번째 수

오늘은 백준(BOJ) 1300번 K번째 수 문제에 대해 다뤄볼 예정이다.

K번째 수 문제 링크 (백준(BOJ) 1300번 문제): https://www.acmicpc.net/problem/1300 

1300번: K번째 수

 

문제 설명 

백준 1300번 K번째 수 문제는 A[i][j] = i×j 값으로 구성된 N X N 배열을 일차원 배열(B)로 옮긴 후, 정렬했을 때 B[k] 값이 무엇인지 구하는 문제이다. 

 

문제 풀이 

이 문제의 핵심은 K값 보다 작은 숫자의 개수를 세어 이분 탐색 알고리즘을 시행하는 것이었다. 

 

예를 들어, 배열의 크기 3과 K값으로 7이 들어왔다고 해보자. 

1	2	3
2	4	6
3	6	9

그럼, 2차원 배열에 이와 같이 만들어지게 된다.

이를 일차원 배열로 옮긴 후 정렬을 하게 되면, 1 2 2 3 3 4 6 6 9 라는 값이 배열에 담기게 될 것이다. 

 

이후, B[k] 값을 찾기 위해 K 값보다 작은 값의 개수를 세어 접근해보자. 

개수를 세기 위해선 mid 값을 각 행으로 나눠주어 더해준다. (단, (mid / i )) > N 경우, N을 더함)  

(여기서 mid / i > N 경우, N을 더하는 이유는 mid / i 가 배열의 범위를 벗어나기 때문이다.)

시작 위치는 1, 끝 위치는 K 값으로 정해준 후, 이분 탐색(Binary Search) 알고리즘을 실행한다. 

 

이를 코드로 나타내면 아래와 같이 구현할 수 있다.