<div id="readability-page-1" class="page">
                
                
                


<div id="wrap">
	
	<hr>
	<section>
		
		<article id="content">
			

			

			

			

			<div>
				

				            
                
	
	
		<div>
			<p>운동하는 개발자/알고리즘, 코딩테스트</p>
			
			<p>
				<span>2023. 12. 11. 21:25</span>
				
			</p>
		</div>
		<div><hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
<h3 data-ke-size="size23"><br>🅰️문제주소 :<span> <a href="https://www.acmicpc.net/problem/1300" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/1300</a></span></h3>
<figure id="og_1702296514310" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="1300번: K번째 수" data-og-description="세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수&nbsp;A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를&nbsp;구해보자. 배열 A와 B" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/1300" data-og-url="https://www.acmicpc.net/problem/1300" data-og-image="https://scrap.kakaocdn.net/dn/cEVKPT/hyUIDv2XkF/4lzpcG8Yy7xO1Gl1pxX7f1/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"><a href="https://www.acmicpc.net/problem/1300" target="_blank" rel="noopener" data-source-url="https://www.acmicpc.net/problem/1300">

<div>
<p data-ke-size="size16">1300번: K번째 수</p>
<p data-ke-size="size16">세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수&nbsp;A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를&nbsp;구해보자. 배열 A와 B</p>
<p data-ke-size="size16">www.acmicpc.net</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/cEVKPT/hyUIDv2XkF/4lzpcG8Yy7xO1Gl1pxX7f1/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"></figure>

<h3 data-ke-size="size23"><br>🚩문제&nbsp;</h3>
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="996" data-origin-height="188"><span data-url="https://blog.kakaocdn.net/dn/pd2NB/btsBMPun1Up/CzYuTaK5hqKtZKsu3Wm5Jk/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/pd2NB/btsBMPun1Up/CzYuTaK5hqKtZKsu3Wm5Jk/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="996" data-origin-height="188"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 문제 그대로 2차원 배열을 만들고 정렬을 시키면 시간복잡도가 N^2으로 초과해버린다.<br>&nbsp;- <span>A[i][j] = i×j<span> 배열에서 두 가지의 규칙을 찾아야 한다.<br></span></span>&nbsp; 1) 해당배열은 k번째 값은 k의 값을 넘지 못한다. (3x3배열에서 마지막 인덱스의 값이 9이므로)<br>&nbsp; 2) 한 행에서 '중앙값을 행으로 나눈 값' vs '열의 수' 둘 중 작은 수는 해당 행에서 중앙값보다 작거나 같은 수의 개수가 된다. 따라서 이 값을 모든 행에서 구한 뒤 합산한 뒤 K와 비교하면 K번째 값이 현재보다 앞쪽에 있는지, 뒤쪽에 있는지 알 수 있다.&nbsp;<br>&nbsp;- 위 규칙에 의해서 '작거나 같은 수의 개수'의 합 값이 K보다 작으면 K값은 더 뒷쪽에 있으므로 시작인덱스 값을 중앙값+1으로 변경한다.<br>&nbsp;- 반대로 '작거나 같은 수의 개수'의 합이 K보다 크거나 같으면 현재 K의 값을 찼았거나 K의 값이 더 앞쪽에 있다는 뜻이므로 임시로 정답에 중앙값을 넣어준 뒤 종료인덱스를 중앙값-1로 변경하고 이진탐색이 종료될 때까지 계속한다.&nbsp;</p>

<h3 data-ke-size="size23">☕코드는 아래 숨김</h3>
<div data-text-less="닫기" data-text-more="더보기" data-ke-type="moreLess"><p><a>더보기</a></p><div>
<pre id="code_1701091944942" data-ke-language="cpp" data-ke-type="codeblock"><code>
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;math.h&gt;
int main() {
	std::ios::sync_with_stdio(false);
	std::cout.tie(0);
	std::cin.tie(0);

	int N, k;

	std::cin &gt;&gt; N;
	std::cin &gt;&gt; k;

	int start = 1;
	int end = k;
	int result = 0;
	while (start &lt;= end) {
		int mid = (start + end) / 2;
		int temp_sum =0;
		for (int i = 1; i &lt;= N; ++i) {
			temp_sum += std::min(N, mid / i);
		}
		if (temp_sum &lt; k) {
			start = mid + 1;
		}
		else {
			result = mid;
			end = mid - 1;
		}
	}

	std::cout &lt;&lt; result;

	return 0;
}</code></pre>
</div>
</div>

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- <span>A[i][j] = i×j<span><span>&nbsp;</span>배열에서 두 가지의 규칙<br></span></span><span>&nbsp; 1) 해당배열은 k번째 값은 k의 값을 넘지 못한다. (3x3배열에서 마지막 인덱스의 값이 9이므로)</span><br><span>&nbsp; 2) 한 행에서 '중앙값을 행으로 나눈 값' vs '열의 수' 둘 중 작은 수는 해당 행에서 중앙값보다 작거나 같은 수의 개수가 된다. 따라서 이 값을 모든 행에서 구한 뒤 합산한 뒤 K와 비교하면 K번째 값이 현재보다 앞쪽에 있는지, 뒤쪽에 있는지 알 수 있다.&nbsp;</span></p>
<p data-ke-size="size18"><span>이걸 모르면 탐색이고 뭐고 시작도 할 수 없다...</span></p>
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
</div>
		

		
			<div>
				<h2><strong>'운동하는 개발자/알고리즘, 코딩테스트'</strong> Related Articles</h2>
				
			</div>
		

		



	

                
            
			</div>

			

			

			

		</article>
	</section>
	<hr>
	
	
</div>







                




        
        











  


        

                
                







                
                


                

</div>

운동하는 개발자

️문제주소 : https://www.acmicpc.net/problem/1300
 
 문제 
 
 
 풀이 
 - 문제 그대로 2차원 배열을 만들고 정렬을 시키면 시간복잡도가 N^2으로 초과해버린다.
 - A[i][j] = i×j 배열에서 두 가지의 규칙을 찾아야 한다.
  1) 해당배열은 k번째 값은 k의 값을 넘지 못한다. (3x3배열에서 마지막 인덱스의 값이 9이므로)
  2) 한 행에서 '중앙값을 행으로 나눈 값' vs '열의 수' 둘 중 작은 수는 해당 행에서 중앙값보다 작거나 같은 수의 개수가 된다. 따라서 이 값을 모든 행에서 구한 뒤 합산한 뒤 K와 비교하면 K번째 값이 현재보다 앞쪽에 있는지, 뒤쪽에 있는지 알 수 있다. 
 - 위 규칙에 의해서 '작거나 같은 수의 개수'의 합 값이 K보다 작으면 K값은 더 뒷쪽에 있으므로 시작인덱스 값을 중앙값+1으로 변경한다.
 - 반대로 '작거나 같은 수의 개수'의 합이 K보다 크거나 같으면 현재 K의 값을 찼았거나 K의 값이 더 앞쪽에 있다는 뜻이므로 임시로 정답에 중앙값을 넣어준 뒤 종료인덱스를 중앙값-1로 변경하고 이진탐색이 종료될 때까지 계속한다. 
 
☕코드는 아래 숨김
더보기
#include <iostream>
#include <vector>
#include <math.h>
int main() {
	std::ios::sync_with_stdio(false);
	std::cout.tie(0);
	std::cin.tie(0);
	int N, k;
	std::cin >> N;
	std::cin >> k;
	int start = 1;
	int end = k;
	int result = 0;
	while (start <= end) {
		int mid = (start + end) / 2;
		int temp_sum =0;
		for (int i = 1; i <= N; ++i) {
			temp_sum += std::min(N, mid / i);
		}
		if (temp_sum < k) {
			start = mid + 1;
		}
		else {
			result = mid;
			end = mid - 1;
		}
	}
	std::cout << result;
	return 0;
}
 
 알게 된 것 
 - A[i][j] = i×j 배열에서 두 가지의 규칙
  1) 해당배열은 k번째 값은 k의 값을 넘지 못한다. (3x3배열에서 마지막 인덱스의 값이 9이므로)
  2) 한 행에서 '중앙값을 행으로 나눈 값' vs '열의 수' 둘 중 작은 수는 해당 행에서 중앙값보다 작거나 같은 수의 개수가 된다. 따라서 이 값을 모든 행에서 구한 뒤 합산한 뒤 K와 비교하면 K번째 값이 현재보다 앞쪽에 있는지, 뒤쪽에 있는지 알 수 있다. 
이걸 모르면 탐색이고 뭐고 시작도 할 수 없다...

Beakjoon] K번째 수 (백준 1300 코테) - 탐색

댓글