2023. 9. 6. 20:43ใCoding Test/BOJ
๐๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ
๐ง๐ปํ์ด ๊ณผ์
N์ด ์ต๋ \( 10^5 \)๋ผ์, ๋น์ฐํ \( \mathrm{O(n^2)}\) ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ๋ก ์ปท ๋นํฉ๋๋ค. ๊ทธ๋ ๋ค๋ฉด, A[i][j] = \( i \times j \)์ผ๋ก ๊ตฌ์ฑ๋๋ 2์ฐจ์ ๋ฐฐ์ด์ ๋ง๋ค ์๊ฐ ์๋ค๋ ์๊ธฐ๊ฐ ๋๋๋ฐ ์ด๋ป๊ฒ ํ์ด์ผ ํ ์ง ๋ง๋งํ์ต๋๋ค. ๊ฒฐ๊ตญ ๋ค๋ฅธ ๋ถ๋ค์ ํํธ๋ฅผ ์ฐพ์์ ์ดํด ๋ดค๋ค์.
์ธ์์ ์ ๋ง ๋๋ํ ์ฌ๋๋ค์ด ๋ง์ ๊ฒ ๊ฐ์ต๋๋ค. ์ด๋ป๊ฒ ์ด๋ฐ ์๊ฐ์ ํด๋ผ๊น๋ ๊ฐํ์ด ๋์ฌ ์ ๋๋ก์.
์ด ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์ํด์๋ ์์์ผ ํ ์์ด๋์ด๊ฐ 2๊ฐ์ง๊ฐ ์์์ต๋๋ค.
๐ก์ฒซ ๋ฒ์งธ ์์ด๋์ด
๋ฌธ์ ์์ ์๊ตฌํ๋ ๋ต์์ \( \mathrm{B[k]} \)์ ๊ฐ์ ๋๋ค.
\( N = 3 \)์ธ 2์ฐจ์ ๋ฐฐ์ด์ 1์ฐจ์ ๋ฐฐ์ด๋ก ํํํ๋ฉด, [1, 2, 3, 2, 4, 6, 3, 6, 9]์ ๋๋ค.
์ด๊ฒ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ฉด [1, 2, 2, 3, 3, 4, 6, 6, 9]์ ๊ฐ์ต๋๋ค.
์์ ๋ต์์์ ๋ณด์ฌ์คฌ๋ ๊ฒ์ฒ๋ผ, \( \mathrm{B[7]} = 6 \)์ ๋๋ค. ํ์ง๋ง, ์ด \( \mathrm{B[7]} = 6 \)์ ๋ค๋ฅด๊ฒ ํด์ํ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ํด์ํ ์ ์์ต๋๋ค.
\( \mathrm{B[7]} = 6 \)์ 6๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ซ์๋ค์ ๊ฐ์๊ฐ 7๊ฐ ์ด์์ด๋ค.
๊ทธ๋ ์ต๋๋ค. \( \mathrm{B[k] = x} \)๋ผ๊ณ ํ์ ๋, 2์ฐจ์ ๋ฐฐ์ด์์ ์ต์๊ฐ์ด 1, ์ต๋๊ฐ์ด \(N^2\)์ด๋ ์ด ์๋ค ์ฌ์ด์์ \(x\)๊ฐ์ ๋ํ ๋งค๊ฐ๋ณ์ ํ์์ ๋ค์ด๊ฐ ์ ์์ต๋๋ค.
ํ์ง๋ง, ํ์ ์กฐ๊ฑด์ ์ด๋ป๊ฒ ์ค์ ํด์ผ ํ ๊น์? ์ฌ๊ธฐ์์ ์ด์ ๋ ๋ฒ์งธ ์์ด๋์ด๊ฐ ํ์ํฉ๋๋ค.
๐ก๋ ๋ฒ์งธ ์์ด๋์ด
์์์ ๋ดค๋ 2์ฐจ์ ๋ฐฐ์ด ์๋ณธ๊ณผ \( x = 7 \)์ด๋ผ๋ ๊ฐ์ ์๋ก ๋ค์ด๋ด ์๋ค.
1 2 3
2 4 6
3 6 9
- 1ํ์์ 7๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ ๊ฐ์๋ 3๊ฐ์ ๋๋ค.
- 2ํ์์ 7๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ ๊ฐ์๋ 3๊ฐ์ ๋๋ค.
- 3ํ์์ 7๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ ๊ฐ์๋ 2๊ฐ์ ๋๋ค.
์ด ๊ฒฝ์ฐ ์ด ๊ฐ์๊ฐ 8๊ฐ์ด๋, \( x = 7 \)๋ณด๋ค ํฌ๋ฏ๋ก ์กฐ๊ฑด์ ๋ง์กฑํฉ๋๋ค. ๊ทธ๋ฐ๋ฐ, ์ด๋ป๊ฒ x๋ณด๋ค ์์ ์ซ์๋ค์ ๊ฐ์๋ฅผ ์ฝ๊ฒ ์ ์ ์์๊น์?
๋ฐฉ๋ฒ์ ๊ฐ๋จํฉ๋๋ค. min((x / ํ ๋ฒํธ), N)์ ์ ํํ๋ฉด ๋ฉ๋๋ค.
- 1๋ฒ์งธ ํ์์๋ min(7 / 1 = 7, 3) = 3์ ์ ํํฉ๋๋ค.
- 2๋ฒ์งธ ํ์์๋ min(7 / 2 = 3, 3) = 3์ ์ ํํฉ๋๋ค.
- 3๋ฒ์งธ ํ์์๋ min(7 / 3 = 2, 3) = 2๋ฅผ ์ ํํฉ๋๋ค.
์ด๋ฐ ์์ผ๋ก x๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ซ์๋ค์ ๊ฐ์๋ฅผ ์ ์ ์์ต๋๋ค.
์ด์ ๊ฐ์๋ฅผ ์ธ๋ ๋ฐฉ๋ฒ์ ์์์ผ๋, ๋งค๊ฐ๋ณ์ ํ์์ ์กฐ๊ฑด์ ์ด๋ป๊ฒ ์ค์ ํด์ผ ํ ๊น์?
x๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ซ์๋ค์ ๊ฐ์๋ฅผ \( T \) ๋ผ๊ณ ํ์ ๋,
- \( T < k \)๋ผ๋ฉด, mid ๊ฐ์ด ๋๋ฌด ์๋ค๋ ์๋ฏธ์ ๋๋ค. ๋ ํค์ธ ํ์๊ฐ ์์ผ๋ฏ๋ก left = mid + 1๋ก ๋ณ๊ฒฝํ์ฌ ์ฌํ์ํฉ๋๋ค.
- \( T \geq k \)๋ผ๋ฉด, mid ๊ฐ์ด ์ ๋ต์ด ๋ ์ ์์ต๋๋ค. ํ์ง๋ง ๋ ์์ mid ์ค์ ์กฐ๊ฑด์ ๋ง๋ ๊ฒ ์์ ์ ์์ต๋๋ค.
- ๋ฐ๋ผ์, min(์ด์ ์ ๋ต mid, ํ์ฌ mid)์ ์ ํํ๊ณ , ํ์ ๋ฒ์๋ฅผ right = mid - 1๋ก ํ์ฌ ๊ณ์ ํ์ํฉ๋๋ค.
- left \( \leq \) right๋ฅผ ๋ง์กฑํ ๋๊น์ง ์์ ์กฐ๊ฑด์ ๋ฐ๋ผ ํ์์ ๊ณ์ํฉ๋๋ค.
์ด๋ฌํ ์์ด๋์ด๋ฅผ ์๊ฐํด๋ด๋ ๊ฒ ์์ฒด๊ฐ ์ด๋ ค์ด ๋ฌธ์ ์ธ ๊ฒ ๊ฐ์ต๋๋ค. ๋ง์ด ์๊ฐํด๋ณด๊ณ , ๋ง์ด ํ์ด๋ณด๊ณ , ๋ง์ด ๊ณ ๋ฏผํด๋ด์ผ ๊ฒ ๋ค์.
โ๏ธ์์ค ์ฝ๋ ๋ฐ ๊ฒฐ๊ณผ
#include <iostream>
#define FAST_IO cout.tie(NULL); cin.tie(NULL); ios::sync_with_stdio(false);
using namespace std;
using uint32 = unsigned int;
// midValue๋ณด๋ค ์์ ์ซ์ ๊ฐ์ ์ฐพ๊ธฐ
uint32 CountNumbersUntil(const uint32 untilNum, const uint32 N)
{
uint32 count = 0;
for (uint32 i = 1; i <= N; i++)
count += min((untilNum / i), N);
return count;
}
int main()
{
FAST_IO
int N, k;
cin >> N >> k;
uint32 minValue = 1, maxValue = N * N;
uint32 answer = maxValue;
// "B[k] = midValue" ์์ midValue๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ซ์๊ฐ k๊ฐ ์ด์์ผ ๋์ midValue๋ฅผ ์ฐพ์๋ผ. (with Binary Search)
while (minValue <= maxValue)
{
uint32 midValue = (minValue + maxValue) / 2;
uint32 countNumsUntilMidValue = CountNumbersUntil(midValue, N);
if (countNumsUntilMidValue < k)
minValue = midValue + 1;
else
{
maxValue = midValue - 1;
answer = min(answer, midValue);
}
}
cout << answer;
return 0;
}
'Coding Test > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] 2110๋ฒ | ๊ณต์ ๊ธฐ ์ค์น (C++) (0) | 2023.10.08 |
---|---|
[BOJ] 2512๋ฒ | ์์ฐ (C++) (0) | 2023.09.06 |
[BOJ] 13335๋ฒ | ํธ๋ญ (C++) (0) | 2023.09.04 |
[BOJ] 1654๋ฒ | ๋์ ์๋ฅด๊ธฐ (C++) (0) | 2023.09.02 |
[BOJ] 1629๋ฒ | ๊ณฑ์ (C++) (0) | 2023.09.01 |