백준 1300번: K번째 수

배영채·2022년 2월 4일
0

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

참고한 블로그 : https://kbw1101.tistory.com/29



2차원 배열 a[i][j] = i x j의 값을 가지고, 이를 1차원배열에 오름차순으로 정렬하여 수를 저장할 때 B[k]의 값이 무엇인지 찾는 문제이다.
N의 최댓값이 10^5 이므로 값을 저장해서 풀려고 하면 10^10만큼의 저장공간이 필요하기 때문에 메모리 초과가 뜬다. 또한 시간 복잡도도 O(N * log N)이어서 시간초과가 뜬다고 한다.

방법이 도저히 생각나지 않아서 블로그를 참고했다. 이런 방법을 어떻게 생각해내시는지 정말 대단하다..
임의의 수 S보다 작은 수들의 개수를 전부 세서 k와 비교하고, 개수가 더 적다면 수가 큰 것이므로 S를 줄이기 위해 end = mid - 1로 바꾸어 다시 진행한다. 개수가 더 많다면 수가 작은 것이므로 S를 키우기 위해 start = mid + 1로 바꾸어 다시 진행한다.

if(sum < k)
	end = mid - 1;
else{
	start = mid + 1;
    result = mid; // 값 저장

또 S보다 작은 수의 개수를 구할 때 2중 for문으로 i x j를 직접 하면서 S와 비교해 그 개수를 구하려고 했는데, 위 블로그에서는 더 간단하게 풀었다. i번째 행에서 S보다 작은 수의 개수는 min(S / i, n)이라고 한다.

왜냐하면, 각 행은 i x 1, i x 2, i x 3, i x 4, ..... , i x j 이기 때문에,
S를 i로 나눈 값에 나머지를 버린 값이 그 행에서 S보다 작거나 같은 개수가 되기 때문이다. ( 블로그에 써진 말 )

글로 풀어서 써진게 이해하기 헷갈릴 수 있는데, 아무튼 무슨 말인지는 알겠다. 그리고 숫자를 대입해서 계산해보면 값이 맞게 나옴을 알 수 있다.

위에 적어왔던 것들로 이분탐색을 진행하면 쉽게 답이 나온다.

<작성한 코드>

#include <iostream>
#define min(a, b) (a < b ? a : b)
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    int s = 1, e = k, mid, result;
    while(s <= e){
        int sum = 0;
        mid = (s + e) / 2;

        for(int i = 1; i <= n; i++)
            sum += min(n, mid / i);

        if(sum < k)
            s = mid + 1;
        else if(sum >= k){
            result = mid;
            e = mid - 1;
        }
    }
    cout << result;
}

블로그를 참고하여 똑같이 코드를 짰는데, n = 5, k = 17을 대입했을 때 자꾸 10이 아니라 11이 나오는 것이었다. 알고 봤더니 while문의 조건에서 = 을 적어주지 않았던 것.. 등호가 자꾸 헷갈린다.

0개의 댓글