- 문제 링크
백준 1300번 - k번째 수
해결 전략
본 문제는 꽤나 까다로운 문제이다. 문제의 해결 Idea를 찾기만 한다면 어렵지 않게 해결할 수 있지만, 그 Idea를 찾는 과정에 '함정으로 빠지기 쉬운 유혹'이 많기 때문이다.
문제를 읽어보고, 몇 가지 예제를 분석하다보면, 많은 이(본인 포함)들이 행렬을 그려보고, 그 안에서 수를 세는데 필요한 규칙성이나, 수식을 찾기 바쁠 것이다. 그런 와중에 N은 10^5까지이다 보니 무언가 log꼴의 알고리즘이 필요할 것만 같은데, 그 알고리즘을 어디에 적용해야할지도 막막하다. 여러 고민거리가 혼재하는, 상당히 난이도가 있는 문제라 할 수 있겠다.
본 문제에서 가장 중요한 해결 Idea는 다음과 같은 발견에서 출발한다. 이 발견을 하는 것이 가장 어렵고, 문제 해결의 관건이라 할 수 있겠다.
B[k] = T의 의미는 무엇인가?
B 배열의 k번째 Index 값이 T이다.
"T라는 값보다 작거나 같은 원소의 개수가 최소 k개가 존재한다."
"T라는 값보다 작거나 같은 원소의 개수가 최소 k개가 존재한다."라는 서술이 굉장히 중요하다. 이 말은 곧 다음으로 확장할 수 있기 때문이다.
T의 값을 '탐색의 기준'으로 두면, 'T라는 값보다 작거나 같은 원소의 개수'만 계산할 수 있다면 문제 해결이 간단해질 것이다.
무엇으로? T 범위가 매우 넓으니, Binary Search같은 방식으로!
그렇다면, 관건은 'T라는 값보다 작거나 같은 원소의 개수'를 계산하는 방법이다. 여기에서도 한 가지 중요한 발견이 필요하다. 이 발견의 경우, 잘 기억해두면 좋을 것이다. 아래를 보자.
4 8 12 16
3 6 9 12
2 4 6 8
1 2 3 4
~> A행렬은 곧 '1 2 3 4' Seqeunce에 1, 2, 3, 4를 곱하고 쌓은 것과 같다. 즉, 구구단 형태라고 볼 수 있는 것이다.
~> 이때, 각 단에서 T보다 작은 원소의 개수를 어떻게 구할 수 있을까?
=> 어렵게 생각하지 말자.
T = 6이라 해보자. 1단(1 2 3 4)에서는 4개 모두 6보다 작다.
2단(2 4 6 8)에서는 2개(2, 4)가 6보다 작다.
3단(3 6 9 12)에서는 2개(3, 6)가 6보다 작거나 같다.
4단(4 8 12 16)에서는 1개(4)가 6보다 작거나 같다.
~> 계산 방법을 발견할 수 있는가? 그렇다. 그냥 단순한 나눗셈이다(좀만 생각해보면 매우 당연하다)!!!
즉, 1~N에 대해, 1~N으로 T를 나누었을 때, 그 몫들의 합이 곧 'T보다 작거나 같은 원소의 개수'이다. 단, 몫이 N보다 커지면 N으로 조정해줘야겠지? 한 단에 N보다 많이 있을 순 없으니까!
이처럼, 두 번의 '중요한 발견'을 통해 본 문제의 해결 Idea를 설계할 수 있다. 두 번의 발견 모두 생각보다 난도가 있기 때문에 본 문제가 어려운 것이다. 여기까지 이해했다면, 구현 자체는 매우 쉬울 것이다.
아래는 정답 코드이다.
#include <iostream>
// BOJ - 1300 kth Number
using namespace std;
typedef long long LL;
LL ans;
void find_value(int n, int k, LL lo, LL hi) {
LL val = (lo + hi) / 2, smalls = 0, temp;
if (lo <= hi) {
for (LL layer = 1; layer <= n; layer++) {
temp = val / layer;
if (temp > n) temp = n;
smalls += temp;
}
if (lo == hi) { ans = lo; return; }
if (smalls < k)
find_value(n, k, val + 1, hi);
else if (smalls >= k)
find_value(n, k, lo, val);
}
}
int main(void) {
LL n, k;
cin >> n >> k;
find_value(n, k, 1, n*n);
cout << ans;
return 0;
}(이때, main 함수에서 n과 k를 long long Type으로 선언해주는 것 역시 중요하다. n*n을 find_value 함수로 넘길 때, 단순히 n을 int로 선언할 경우, n이 10^5까지 가능하기 때문에 n*n 임시 계산에서 Overflow가 발생할 수 있다)
