[백준] 1300 k번째 수

March 23, 2021 ( last updated : March 23, 2021 )
이분탐색 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 1300번 k번째 수

[백준] 1300번 k번째 수

백준 1300번

알고리즘 유형

문제 이해

솔직히 처음에는 이해를 못해서 못풀었다. 이해를 못한 부분은 다음 구문이다.

배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다.

B의 크기가 N×N이 된다는데 무슨 소린가 했다. 알고보니 일차원 배열 B의 길이가 N×N이 된다는 것이었다. B[N×N]인 것이다. 자 그럼 이제 B[k]를 구하는 방법에 대해서 얘기해보자

풀이 방법

골드 3문제인데 내용자체는 심플해서 놀랐다. 근데 역시나 N은 10의 5승 만큼 가능하다는 소리에서 부터 A와 B 배열을 만들어서 정렬하는 것은 안될 것 같다는 생각이 들었다. A의 배열은 안만들어 봐도 어떻게 생겼을지 알고 있기 때문에 해당 속성을 이용해야될 것이라고 생각했다.

ij 1 2 3 4 5
1 1 2 3 4 5
2 2 4 6 8 10
3 3 6 9 12 15
4 4 8 12 16 20
5 5 10 15 20 25

자 규칙이 보이는가? 보이긴 개뿔 구글링 타임이다.
농담이다. 그렇게 쉽게 포기하진 않는다.

우리가 구할 것은 B 배열의 k번째 수보다 작은 수의 숫자들을 구할 것이다. 먼저 k번째 수를 가정한다. 그리고 해당 숫자보다 낮은 수들이 몇 개인지 확인하고 확인한 결과가 k와 같다면 그 수가 k번째의 수인 것이다. 이러한 탐색을 쉽게하는 방법은 이분탐색이 좋다.

이분탐색으로 처음과 끝의 수를 정하고 예측하는 중간 값을 변화해가면서 k번째 수를 예측해 나가겠다. 먼저 이 문제에서 가장 발상이 필요한 곳은 mid로 정한 수 보다 낮은 수들이 몇개인지 확인하는 것이다. 그래프를 다시보자.

ij 1 2 3 4 5
1 1 2 3 4 5
2 2 4 6 8 10
3 3 6 9 12 15
4 4 8 12 16 20
5 5 10 15 20 25

k번째 수가 7이라고 가정해보자.

1 2 3 4 5
5 3 2 1 1

열에 따라서 위와 같이 나온다. 각각 7/i 만큼의 갯 수가 나온다는 것을 알 수 있다. 하지만 한 열에 N개를 넘을 수 없으므로 min(m/i, N )을 해줘야한다.

이해가 안가는 부분은 다음 코드를 보면서 이해한다.

#include <algorithm>
#include <iostream>

using namespace std;

long long N, K;

void solve();

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

  solve();
  return 0;
}

void solve() {
  long long l, h, m, ans = 1;
  long long cnt = 0;

  h = K + 1;
  l = -1;

  while (l + 1 < h) {
    m = (h + l) / 2;
    cnt = 0;

    for (long long i = 1; i <= N; i++) {
      cnt += min(N, m / i);
    }

    if (cnt < K) {
      l = m;
    } else {
      ans = m;
      h = m;
    }
  }
  cout << ans;
}

Originally published March 23, 2021
Latest update March 23, 2021

Related posts :

{# #}