[백준/C++] 1300번. K번째 수

[백준/C++] 1300번. K번째 수

1. 문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

2. 입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다.

3. 출력

B[k]를 출력한다.

4. 풀이

참고 블로그

• 이분 탐색 문제
• 이분 탐색으로 적절한 값을 찾는다.
• start를 0으로 end를 k로 설정했다.
• mid의 의미는 B[k]의 값 후보이다.
• 각 행 마다 mid 값보다 작거나 같은 수의 개수를 result에 더한다.
  각 행의 수열은 n, 2n, 3n, 4n ... 과 같은 방식으로 진행된다.

for (int i = 1; i <= n; i++) {
      result += min(n, mid / i);
    }

• min함수를 사용하지 않으면 있지도 않은 수를 셀 수 있다.
• mid / i를 하면 i행에서 mid 보다 작은 값의 개수를 구할 수 있다.
• result 값이 k 보다 작으면 아직 k번째 수까지 도달하지 못했기 때문에 더 mid를 증가시켜 주어야 한다.
• result 값이 k 보다 크면 k번째 수 이상이기 때문에 현재 값을 answer 변수에 저장하고 이진 탐색을 계속한다.
• result가 k보다 큰 값 중에서 가장 작은 값을 찾아야 정답이다.

5. 처음 코드와 달라진 점

• int 범위로 안 될 줄 알았는데 result 말고는 모두 int안에서 해결이 가능했다.
• n을 입력 받는 코드를 어딘가에 날려먹어서 결과 값이 계속 안 나왔다.
  그냥 안 나오는 것도 아니고 터무니 없게 나와서 울화통이 터질 뻔 했다.

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, k;

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin >> n >> k;
  int start = 1;
  int end = k;
  int answer = 0;

  while (start <= end) {
    int mid = (start + end) / 2;
    long long result = 0;

    for (int i = 1; i <= n; i++) {
      result += min(n, mid / i);
    }
    
    if (result < k) {
      start = mid + 1;
    }
    else {
      answer = mid;
      end = mid - 1;
    }
  }
  
  cout<<answer;
}