[BOJ] 1300 - K번째 수

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

BOJ - K번째 수

문제 유형: 매개변수 탐색(parametric search), 이진 탐색, 행렬

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

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

 

입력

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

 

출력

B[k]를 출력한다.

 

풀이

n이 정해져 있고 2D배열 A에서 x이하의 개수를 찾으려면 어떻게 해야 할까?

 

행렬에 작게 써보면, 규칙이 보일 것이다! 위 그림에서는 n=7인경우, x이하의 개수를 찾고 있다.

아래와 같다는 것을 알 수 있다.

parametric search를 통해서, 초기 lo = 1, 초기 hi = k(k를 초과하는 정답이 나오지 않는다는 것은 보장된다. 1은 1개, 2는 2개, 3은 2개.. 와 같이 조합의 수가 반드시 k를 초과하므로, k이하 내에서 답을 찾는 것이 빠르다.)

mid = (lo + hi)/2를 구해서, 행렬에서 mid이하의 개수를 찾는다.

개수가 k이상이라면, mid는 가능한 수라는 의미이므로, 더 범위를 낮춰서 시도해본다. 혹시나 더 작은 수로 만족될 수도 있기 때문이다.

k미만이라면, mid의 크기를 키운다.

 

최종적인 수는 마지막으로 cnt >= k였던 mid값이 된다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n, k;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> k;

  int lo = 1, hi = k;
  int ans = 0;

  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    ll cnt = 0;
    for (int i = 1; i <= n; ++i) {
      cnt += min(mid / i, n);
    }

    if (cnt >= k) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }

  cout << ans << "\n";

  return 0;
}

 

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, k int32
	fmt.Fscan(reader, &n, &k)

	lo := int32(1)
	hi := k
	var ans int32
	for lo <= hi {
		mid := (lo + hi) / 2
		cnt := int32(0)
		for i := int32(1); i <= n; i++ {
			cnt += min(n, mid/i)
		}

		if cnt >= k {
			ans = mid
			hi = mid - 1
		} else {
			lo = mid + 1
		}
	}

	fmt.Fprintln(writer, ans)

}