백준 1300 k번째 수

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

1300번: K번째 수

 

 

EXPLANATION

 

 

A[N][N]의 배열을 B[N*N]배열에 옮긴 후 sort 함수로 정렬한 후 b[K]의 값을 출력하면 시간 초과 뜬다.

N의 범위가 100,000까지이므로 최악의 경우 N*N이 100,000^2이다.

뿐만 아니라, A[100001][100001]의 배열 또한 메모리 초과로 사용할 수 없다.

따라서 단순히 배열을 오름차순으로 정렬하는 방법으로 문제를 풀 수 없고,

이분 탐색을 이용해 빠르게 답을 수할 수 있다.

 

이분 탐색으로 mid값의 index가 목표 index K를 찾아가면 된다. (목표 index K로 수렴시키기)

 

mid값 원소의 index를 찾는 법:

mid를 원소로 가지는 가장 큰 idnex를 시간 초과 없이 찾을 수 잇다.

long long count(long long mid)
{
	long long sum = 0;
	for (int i = 1; i <= N; i++)
	{
		sum += min(mid / i, N);
	}
	return sum;
}

ex)

N = 16일 때,

첫번째 left = 1, right = 4*4 = 16, mid = 8이고,

8의 값을 가지는 원소들 중 index가 가장 큰 값:

[ i ][ j ]	[1]	[2]	[3]	[4]
[1]	1	2	3	4
[2]	2	4	6	8
[3]	3	6	9	12
[4]	4	8	12	16

i가 1일 때,

1, 2, 3, 4, .... , 7, 8    <= 8

mid / i =  8.

min( mid/i, N) = 4.

 

i가 2일 때,

2, 4, 6, 8     <= 8

mid / i =  4.

min( mid/i, N) = 4.

 

i가 3일 때,

3,  6    <= 8

mid / i =  2.

min( mid/i, N) = 2.

 

i가 4일 때,

4,  8    <= 8

mid / i =  2.

min( mid/i, N) = 2.

 

mid 8을 원소로 가지는 가장 큰 idnex는 4 + 4 + 2 + 2 = 12

K	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
B[K]	1	2	2	3	3	4	4	4	6	6	8	8	9	12	12	16

 

이 방법으로 index를 구하면 for문 하나이므로 시간 복잡도 O(N)만에 index를 구할 수 있다.

 

 

자 mid값 원소의 index를 구하는 방법을 알아보았으니,

이분 탐색으로 mid값의 index가 목표 index K로 수렴시켜보자.

예제를 가지고 살펴보자.

 

예제 입력

3
7

left	right	mid	count(mid)	mid vs K
1	16	8	12	12 >= 7
1	7	4	8	8 >= 7
1	3	2	3	5 < 7
3	3	3	5	5 < 7
4	3	3	5	5 < 7

 

참고: https://cocoon1787.tistory.com/292

 

 

CODE

#include <iostream>
#include <algorithm>
using namespace std;

long long N, K;
long long l, r, mid;
long long cnt;

long long count(long long x)
{
	long long sum = 0;
	for (int i = 1; i <= N; i++) 
        sum += min(x / i, N);
    
	return sum;
}

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

	l = 1;
	r = N * N;

	while (l <= r)
	{
		mid = (l + r) / 2;    // Mid보다 작거나 같은 수들의 개수

		cnt = count(mid);

		if (cnt >= K) 
        {
            // Mid보다 작거나 같은 수들의 개수가 목표 인덱스보다 많으므로
			// 이므로 Mid값을 더 작게 찍어줘야 합니다.
			// 따라서 High값 조정
            r = mid - 1;
        }
		else 
        {
            // Mid보다 작거나 같은 수들의 개수가 목표 인덱스보다 작으므로
			// 이므로 Mid값을 더 크게 찍어줘야 합니다.
			// 따라서 Low값 조정
            l = mid + 1;
        }
	}
    
	cout << l;
}

 

 

 

wak8835  

전역 변수로 left, right를 선언하면 left, right에 대해서 error: reference is ambiguous가 발생.

 

보통의 ambiguous(모호함) 에러는 전역에 설정한 변수 또는 함수 선언들이 
기존의 함수와 동일한 이름으로 등록하여 사용하려는 경우 일어납니다.

 

std::ios_base& std::left(std::ios_base&)
std::ios_base& std::right(std::ios_base&)

 

우회하는 방법은 전역이 아닌 지역 선언을 하여 사용하는 방법이 있습니다.
(예를 들어, main 함수 안에 지역 변수로 left, right를 선언하여 사용)

대부분의 코테나 알고리즘 관련 대회 시에는
코드상의 복잡도를 최대한 줄이기 위에서 전역 선언을 하는 추세로

max를 mx, maxx 로,
y0을 cy0, y00, _y0 으로.
임시적 방편으로 충돌이 없게 사용하는 편이지만, 

 

변수명이나 차후 코드 유지보수함에 있어서는
지역변수로 선언하여 활용하시는 것이 보다 유리합니다.

 

 

 

지역변수로 left, right를 사용한 백준 2110 공유기 설치 문제(풀이 보러가기).