출처: 백준 알고리즘
주소: 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

문제 요약:
(1) (N, N)인 배열 A을 (1, N2)인 배열 B에 대입
(1-1) 배열 A[i][j]의 값은 i * j 이다.
(2) 배열 B를 오름차순 정렬
(3) 배열 B의 K번째 수를 출력 (단, 배열의 인덱스는 1부터 시작)
문제 해결:
1) 배열 A를 만들어서 배열 B에 대입해서 K번째를 출력하는 방법
=> 처음에는 이렇게 진행하면 쉽게 할 수 있을텐데, 왜 이분 탐색 문제인지를 몰랐다.
=> 하지만, 이렇게 진행하게 되면 많은 양의 메모리가 발생하게 된다.
=> 따라서, 배열을 만들지 않고 배열 B의 K번째 수를 출력해야 하는 방법을 찾아야 한다.
2) 배열 B의 K번째 수를 탐색하는 변수로 계산하여 해당 값을 출력하는 방법
=> 먼저, 간단한 예시를 통해 이해를 해보자.

=> 배열 A를 만들면 위와 같다. 이 배열 A를 배열 B로 만들고 정렬을 하면 아래와 같다.

=> 여기서 K번째 수는 6이다.
=> 정렬된 배열 B에서 K번째 수라는 것은 1번째 수부터 (k-1)번째 수보다 크거나 같은 수라는 뜻이다.
따라서, 2)번으로 푸는 방법의 알고리즘은 아래와 같다.
(1) n과 k를 입력받는다.
(2) 1 ~ N2만큼 탐색을 진행한다.
(2-1) 찾고자하는 값의 시작하는 값(start), 마지막 값(end), 중간 값(mid)으로 설정
(3) start <= end를 만족하는 동안 반복하면서 탐색
(3-1) 찾고자하는 값이라고 예상하는 중간 값(mid)보다 작거나 같은 값의 개수를 cnt로 설정
(3-2) cnt < k이면, start = mid + 1으로 설정
(3-3) cnt >= k이면, end = mid - 1으로 설정하고 cnt와 k가 같을 수도 있기 때문에 정답에 mid값을 저장
(3-4) mid = (start + end) / 2으로 중간 값을 갱신
(4) 정답으로 저장한 값 출력
=> 여기서, 정렬된 배열 B를 보면 배열 B의 값은 해당 인덱스보다 클 수 없다.
=> 따라서, 탐색을 하는 범위(알고리즘 2번)를 1 ~ k로 한정해도 된다.
소스 코드:
#include <iostream>
#include <algorithm>
#include <cmath>
void solve(int start, int end, int n, int k) {
int mid = (start + end) / 2;
int res = 0;
while (start <= end) {
int cnt = 0;
// 2차원 배열 A의 값들을 행마다 비교했을 때,
// mid보다 작은 값이 몇 개가 있는 지 계산
// 배열 A의 행을 i로 나눈 값과 mid/i를 비교하는 것과 동일 for (int i = 1; i <= n; i++) {
cnt += std::min(mid / i, n);
}
// mid보다 작은 값의 개수(cnt)가 k보다 작은 경우
if (cnt < k) {
start = mid + 1;
}
// mid보다 작은 값의 개수(cnt)가 k보다 크거나 같은 경우
// 같은 경우도 계산하는 경우는 같은 값이 2개 존재하기 때문이다.
else {
res = mid;
end = mid - 1;
}
mid = (start + end) / 2;
}
printf("%d\n", res);
}
int main() {
int n, k;
scanf("%d", &n);
scanf("%d", &k);
// 1 ~ n^2 만큼 탐색을 진행해야 한다.
// 하지만, k번째의 수는 k보다 클 수가 없다.
solve(1, k, n, k);
return 0;
}
|
cs |
한줄평:
-> 정렬된 K번째 수는 앞에 자신보다 작거나 같은 수가 K-1개 있다는 의미로 해석할 수 있다.
'알고리즘 > 백준' 카테고리의 다른 글
1927번 - 최소 힙 (0) | 2021.04.05 |
---|---|
11279번 - 최대 힙 (0) | 2021.04.02 |
2110번 - 공유기 설치 (0) | 2021.03.29 |
11401번 - 이항 계수 3 (0) | 2021.03.01 |
1676번 - 팩토리얼 0의 개수 (0) | 2021.01.20 |