PS/Baekjoon Online Judge
[백준 1300] K번째 수 [C]
kimyoungrok
2021. 8. 14. 21:32
728x90
풀이
i * j로 구성된 N x N크기의 배열의 수들을 작은 오름차순으로 나열했을 때, K번째 수가 무엇인지 알아내는 문제다.
N = 3, K = 7일 때,
K번째 수는 다음과 같다.
K | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
i*j | 1 | 2 | 2 | 3 | 4 | 4 | 6 |
즉 임의의 수 mid에 대해 i*j <= mid 만족하며,각 행(i)에서 열(j)들의 개수가 K와 일치할 때까지 탐색하면 된다.
단, 열(j)의 개수는 N을 초과할 수 없다.
for (int i = 1; i <= N; i++)
cnt += min(N, mid/i);
소스코드
#include <stdio.h>
#define min(a,b) a < b ? a : b
int main(){
int N, K;
scanf("%d %d", &N, &K);
int first = 1, last = K;
while (first <= last){
int mid = (first+last)/2, cnt = 0;
for (int i = 1; i <= N; i++)
cnt += min(N, mid/i);
if (cnt < K) first = mid + 1;
else last = mid - 1;
}
printf("%d", last+1);
}
출처
1300번: K번째 수
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B
www.acmicpc.net
728x90