백준 1300 K번째 수

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 N*N배열이 있을 때 이 배열엔 i*j의 숫자가 들어있다고 하고 이 배열을 일차원 배열에 오름 차순으로 정렬 할때 K번째 수를 구하는 문제입니다.

처음에 분류가 이분탐색으로 되어 있어서 그렇게 생각하고 봤는데도 접근을 잘 못하겠어서 다른 글들을 참고하였습니다.

 

우선 배열에 i*j의 숫자들이 저장 되어 있으므로 K보다 작은 숫자의 개수를 찾고 싶다면 K/i를 해야 구할 수 있다는 것이 포인트입니다.

문제의 예시를 보면 N이 3이고 K가 7일때를 예로 들고 있습니다. 이경우 

3*3 배열이므로 아래와 같이 수가 있고 예를 들어 7보다 작은 숫자의 개수를 찾고 싶다면 7/1 + 7/2 + 7/3 을 하는데 이때 7/1 같은경우 7이라는 숫자가 나옵니다. 따라서 몫이 N보다 큰경우는 그 개수가 N개인것과 동일하므로 min(K/i, N) 이라는 식을 사용해야 하는 것을 알 수 있습니다.

1 2 3

2 4 6

3 6 9 

자 그렇다면 이제 여기에 이분탐색을 적용시켜 시작 위치를 1로 끝 위치를 K로 하여서 진행을 해주면 됩니다.

위의 예시로 진행과정을 보면 start = 1 end = 7 이므로 mid 지점은 4가 됩니다.

따라서 총 개수는 3+2+1로 6개 입니다. K가 7이므로 start를 mid+1인 5로 바꿔줍니다.

2번째 과정에서 mid는 6이므로 6을 대상으로 계산을하면 3+3+2 = 8개가 나옵니다.

이제 8은 K보다 크므로 result에 mid값을 넣어주고 end에 mid-1을 넣어줍니다.

3번째 과정은 start = 5 end = 5 이므로 mid가 5가나옵니다. 이때 총 개수는 3+2+1 = 6개입니다.

start와 end가 동일하므로 마지막 과정이고 5보다 작은수는 6개이고 6보다 작은수는 8개이므로 7번째 수는 6이라는 것이 나오게 됩니다.

처음에 이해가 잘 안되었는데 이렇게 직접 예시를 들어서 생각하면 이해가 잘 되는 것 같습니다. 이분탐색 문제는 이 문제가 이분탐색으로 푸는게 맞는가 를 생각하는것이 어려운 것 같습니다.

 

다음은 코드입니다.

 

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,k;
	cin >> N >> k;
	int start = 1;
	int end = k;
	int result = 0;
	while(start <= end) {
		int mid = (start + end) / 2;
		long long num = 0;
		for(int i = 1; i <= N; i++)
			num += min(mid/i, N);
		if(num < k)
			start = mid + 1;
		else {
			result = mid;
			end = mid - 1;
		}
		cout<<start<<' '<<end<<' '<<mid<<'\n';
			
	}
	cout<<result;
	return 0;
}