[BOJ] 1300๋ฒˆ | K๋ฒˆ์งธ ์ˆ˜ (C++)

2023. 9. 6. 20:43ใ†Coding Test/BOJ

๐Ÿ”—๋ฌธ์ œ ๋ณด๋Ÿฌ๊ฐ€๊ธฐ
 

1300๋ฒˆ: K๋ฒˆ์งธ ์ˆ˜

์„ธ์ค€์ด๋Š” ํฌ๊ธฐ๊ฐ€ N×N์ธ ๋ฐฐ์—ด A๋ฅผ ๋งŒ๋“ค์—ˆ๋‹ค. ๋ฐฐ์—ด์— ๋“ค์–ด์žˆ๋Š” ์ˆ˜ A[i][j] = i×j ์ด๋‹ค. ์ด ์ˆ˜๋ฅผ ์ผ์ฐจ์› ๋ฐฐ์—ด B์— ๋„ฃ์œผ๋ฉด B์˜ ํฌ๊ธฐ๋Š” N×N์ด ๋œ๋‹ค. B๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌํ–ˆ์„ ๋•Œ, B[k]๋ฅผ ๊ตฌํ•ด๋ณด์ž. ๋ฐฐ์—ด A์™€ B

www.acmicpc.net

 

๐Ÿง‘‍๐Ÿ’ปํ’€์ด ๊ณผ์ •

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;
}

 

728x90
๋ฐ˜์‘ํ˜•