https://www.acmicpc.net/problem/1300
1300번: K번째 수
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B
www.acmicpc.net
문제에서 제시한 B[K] 가 K번째로 큰 수 이니까
K를 다르게 해석해보자면 B[K] 보다 작거나 같은 수가 K개 있는 것이 된다.
그래서 B[K]를 mid로 잡고 파라메트릭 서치하면서
개수만 세주면 K에 대한 답을 구할 수 있다.
B[K] 가 mid로 잡힌거기때문에 파라메트릭 구간의 끝값이 N*N 인줄 알았는데
AC코드까보니까 K도 된다고하는데
왜인지는 모르겠다.
:question_mark:
더보기
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N,K;
int search(ll s, ll e){
ll mid = (s+e)/2;
ll cnt = 0;
if(s>e) return s;
for(int i=1; i<=N; i++) cnt += min(N,mid/i);
if(cnt < K) return search(mid+1,e);
else return search(s,mid-1);
}
int main(){
cin >> N >> K;
cout << search(1,N*N);
return 0;
}G2치곤 그리 어렵진 않았던거같은데 ㅁㄴㅇㄹ
반응형