[백준] 1300번 : K번째 수

문제

 

---

풀이

 

별별 뻘짓을 많이 했다...

일단 당연히 nxn의 배열을 실제로 저장한다거나, 배열 B를 만든다거나 하면 안된다.

 

/*

생각(aka. 뻘짓)

일단 4x4의 행렬을 그려봤다. 그러다가 놀라운 사실을 하나 발견했다.

i+j=2k(짝수라는 뜻)인 모든 A[i][j]에 대해 A[k][k]가 가장 크다는 것이었다.

그니까...4x4 행렬이 있다고 하자. A[2][2] = 4이다. i+j=4인 다른 A[i][j]를 보면, A[1][3] = 3, A[3][1] =3이 있다.

그래서 이걸 보고 left를 (1, 1), right를 (n, n)으로 한 뒤 그 둘의 mid를 구해서 계산하고 어쩌구...하는 식으로 했는데...망했다.

*/

 

결국 검색을 했고 내 접근이 반은 맞고 반은 틀렸다는 것을 알았다. 반까지는 아니고 45%정도 맞았을까...

하늘색으로 칠한 1열은 1의 배수이다. 2열은 2의 배수이고...그니까 n열은 n의 배수인 것이다.

 

이 4x4 행렬에서 4보다 작거나 같은 수는 총 몇 개가 있을까?

 

1열 : 4/1=4개

2열 : 4/2=2개

3열 : 4/3=1개

4열 : 4/4=1개

 

그니까 j열에서 4보다 작거나 같은 수는 4/j개라는 것이다.

이대로 일반화가 가능할까? 아니다.

 

6보다 작거나 같은 수를 찾아보자. 계산에 따르면 1열에 총 6/1=6개가 있어야 한다.

하지만 그렇지 않다. 이건 4x4행렬이기 때문에 각 행은 많아봐야 4개이기 때문이다.

 

그럼 다시 일반화 하면

nxn행렬이 있을 때, j열에서 숫자 M보다 작거나 같은 수는 min(n, M/j)가 되겠다.

---

이제 이분 탐색으로 특정 수 M을 얻어내고 주어진 행렬에서 M이 몇번째로 큰 수인지 알 수 있게 됐다.

크기 순으로 정렬한 행렬에서 M의 순서를 f(M)이라고 하자.

그럼 보통의 이분 탐색 함수처럼 k==f(M)이면 바로 리턴하고 k<f(M)이면 왼쪽을, k>f(M)이면 오른쪽을 탐색하면 될까?

 

그러면 안되는 반례가 N=3, k=6이다.

만약 방금 말한 논리로 코드를 작성하고 해당 테스트 케이스를 입력하면 5가 나올 것이다. 참고로 답은 4다.

 

이런 문제가 발생하는 이유는 우리가 연속된 숫자를 탐색하는 것과 달리 행렬에는 불연속적인 부분이 있기 때문이다.

3x3 행렬이 있다고 할 때, 1~9까지의 수에 대해 이보다 작은 행렬의 원소 갯수를 세보겠다.

 

3x3 행렬에 실제 존재하는 수만 회색으로 칠했다.

이걸 보면 우리가 찾는 수는 k==f{M}인 수 중에 가장 작은 수 그니까 lower bound라는 것을 알 수 있다.

 

lower bound가 되는 이유는 간단하다.

5보다 작거나 같은 수가 4보다 작거나 같은 수보다 많아지려면 행렬에 5가 있어야 하는데 그렇지 않으니 4보다 작거나 같은 수와 5보다 작거나 같은 수가 같아지는 것이다.

6은 행렬에 실제로 존재하기 때문에 (4보다 작거나 같은 수의 개수)+(행렬에 존재하는 6의 개수)가 6보다 작거나 같은 수의 개수가 된다.

---

그럼 마지막으로, right 값을 뭘로 해야할까?

right의 초기값은 k로 한다. 직접 해보면 알겠지만 f(k)는 항상 k보다 크거나 같다.

그렇기 때문에 우리가 찾는 값이 k보다 크진 않을 것이다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
ll N, k;

ll cntLower(ll num) {
    ll cnt = 0;

    for (ll i = 1; i <= N; i++)
        cnt += min(num / i, N);
    return cnt;
}

ll lowerSearch(ll left, ll right) { //lower bound를 구해야 함
    while (left <= right) {
        ll mid = (left + right) / 2;
        if (k <= cntLower(mid))  //왼쪽 탐색
            right = mid - 1;
        else if (k > cntLower(mid)) //오른쪽 탐색
            left = mid + 1;
    }
    return right + 1;
}

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

    cout << lowerSearch(1, k);
}

전체 소스코드다.

 

myunji.tistory.com/263

[백준] 10816번 : 숫자 카드 2

lower bound 코드에 대한 설명은 여기 있다.

 

ll cntLower(ll num) {
    ll cnt = 0;

    for (ll i = 1; i <= N; i++)
        cnt += min(num / i, N);
    return cnt;
}

특정 수 num에 대해 행렬에 num보다 작거나 같은 수가 몇 개 있는지 계산하는 함수다.

풀이를 그대로 함수로 옮긴거라 굳이 설명을 할 필요는 없을 것 같다.