백준 1300번 K번째 수

- 문제 설명

 

배열 A는 크기가 N*N 인 2차원 배열, 배열 B는 크기가 N*N 인 1차원 배열

A[i][j] = i * j 로 이루어진 2차원 배열의 모든 원소를 배열 B에 넣고 오름차순 정렬했을 때 B[k]의 값을 구하는 문제

※ 배열 A와 B의 인덱스는 1부터 시작한다.

 

 

- 입력

 

첫째 줄에 배열의 크기 N (1 <= N <= 10⁵), 둘째 줄에는 k (1 <= k <= 10⁹)

 

 

- 출력

 

B[k]

 

 

* 문제 풀이의 핵심

 

1. 이분탐색을 적용해야 한다. (최소값 : 1, 최대값 : N * N)

 

 

2. 연산 과정 중 int 형의 범위를 벗어나는 경우가 존재한다.

 

ex) N=10000 일 때,

 

- mid = (left + right) / 2 연산 시 (left + right) 가 int 형 범위 초과

 

- cnt, ret 를 구하는 과정에서 int 형 범위 초과

 

 

3. 나누기 연산의 몫을 통해서 특정 숫자가 몇 번째 인덱스에 위치하는지 알 수 있다.

 

ex) N = 3

배열 A

1 2 3

2 4 6

3 6 9

 

배열 B

1 2 2 3 3 4 6 6 9

 

숫자 6 이하의 숫자 개수 : 8개

1행 : 6 / 1 = 6 (1 2 3)

2행 : 6 / 2 = 3 (2 4 6)

3행 : 6 / 3 = 2 (3 6)

 

숫자 2 이하의 숫자 개수 : 3개

1행 : 2 / 1 = 2 (1 2)

2행 : 2 / 2 = 1 (2)

3행 : 2 / 3 = 0 ()

 

 

- 소스코드

 

#include<iostream>

using namespace std;

long long find_idx(long long mid, long long N) {
	long long ret = 0;

	int i;
	for (i = 1; i <= N; i++) {
		long long cnt = 0;
		if ((mid / i) >= N) { cnt = N; }
		else { cnt = (mid / i); }
		ret += cnt;
	}

	return ret;
}

int main() {
	long long N;
	cin >> N;

	int k;
	cin >> k;

	long long left = 1;
	long long right = (N * N);
	while (left < right) {
		long long mid = (left + right) / 2;
		if (find_idx(mid, N) >= k) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}

	cout << left << "\n";
}

 

 

- 문제링크 : https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

 

- 제출한 코드

 

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요