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


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

			

			

			

			<div>
				

				            
                
	
	
		<div>
			<p>운동하는 개발자/알고리즘, 코딩테스트</p>
			
			<p>
				<span>2023. 12. 21. 22:31</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/1016" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/1016</a></span></h3>
<figure id="og_1703164803143" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="1016번: 제곱 ㄴㄴ 수" data-og-description="어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/1016" data-og-url="https://www.acmicpc.net/problem/1016" data-og-image="https://scrap.kakaocdn.net/dn/sbeMt/hyUPz7sLAX/6FngDmyzgXCLKId6W4eg8K/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"><a href="https://www.acmicpc.net/problem/1016" target="_blank" rel="noopener" data-source-url="https://www.acmicpc.net/problem/1016">

<div>
<p data-ke-size="size16">1016번: 제곱 ㄴㄴ 수</p>
<p data-ke-size="size16">어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수</p>
<p data-ke-size="size16">www.acmicpc.net</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/sbeMt/hyUPz7sLAX/6FngDmyzgXCLKId6W4eg8K/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="1171" data-origin-height="173"><span data-url="https://blog.kakaocdn.net/dn/6r6Bo/btsCqv3Rh2y/RmnOI2JnUYVGhRsd8tBBY0/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/6r6Bo/btsCqv3Rh2y/RmnOI2JnUYVGhRsd8tBBY0/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="1171" data-origin-height="173"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- <span>에라토스테네스의 체를 응용해야 한다. 제곱수로 나누어 떨어지지 않는 수를 찾아야 하므로 반대로 제곱수를 계속 곱해가며 지워나가야 한다.<br>&nbsp;- 값이 무엇인지가 중요한 게 아니라 개수만 체크하면 되기에 bool타입의 배열을 사용한다.<br>&nbsp;- min과 max의 값이 엄청 크므로 overflow에 주의해야 한다.<br>&nbsp;- 추가로 메모리 사용에도 주의해야 한다</span></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>//no 40
#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);

	unsigned long long min, max;

	std::cin &gt;&gt; min &gt;&gt; max;

	std::vector&lt;bool&gt; check(max - min + 1, false);

	for (unsigned long long i = 2; i &lt;= std::sqrt(max); ++i) { //2의 제곱수 부터 체크하기 시작
		unsigned long long pow = i * i;
		unsigned long long start = min / pow; //몇배수 부터 체크해야하는지 시작점을 잡기 위함
		//만약 MIN값이 6이면 시작점은 8이 될것이다(7은 제곱수가 아니므로) 그러기 위해서는 나머지가 있을때 
        //1을 더해주어야 한다 단순 몫으로 구하면 시작값 6보다 작은 4부터(4*1) 찾게된다
		if (min % pow != 0) 
			start++;

		for (unsigned long long j = start; pow * j &lt;= max; ++j) {
			check[(pow * j) - min] = true;
		}
	}
	
	unsigned long long result = 0;

	for (unsigned long long i = 0; i &lt; check.size(); ++i) {
		if (!check[i])
			result++;
	}

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

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

<h3 data-ke-size="size23">💡느낀점&nbsp;</h3>
<p data-ke-size="size18"><span><span>&nbsp;-</span> 에라토스테네스의 체 응용방법</span><span> <br>&nbsp;- 기존 문제처럼 max값만큼 배열선언 시 메모리 초과 오류가 발생한다. 배열의 크기를 최소화할 수 있게&nbsp; &nbsp; max-min을 해주어야 한다</span><br><span>&nbsp;- max-min을 해주는 문제점 때문에 배열의 인덱스값을 실제 값과 동일하다고 볼 수 없다 -&gt; 그러므로 시작점을 구하는 작업을 추가로 해주어야 한다.</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/1016
 
 문제 
 
 
 풀이 
 - 에라토스테네스의 체를 응용해야 한다. 제곱수로 나누어 떨어지지 않는 수를 찾아야 하므로 반대로 제곱수를 계속 곱해가며 지워나가야 한다.
 - 값이 무엇인지가 중요한 게 아니라 개수만 체크하면 되기에 bool타입의 배열을 사용한다.
 - min과 max의 값이 엄청 크므로 overflow에 주의해야 한다.
 - 추가로 메모리 사용에도 주의해야 한다
 
 
☕코드는 아래 숨김
더보기
//no 40
#include <iostream>
#include <vector>
#include <math.h>
int main() {
	std::ios::sync_with_stdio(false);
	std::cout.tie(0);
	std::cin.tie(0);
	unsigned long long min, max;
	std::cin >> min >> max;
	std::vector<bool> check(max - min + 1, false);
	for (unsigned long long i = 2; i <= std::sqrt(max); ++i) { //2의 제곱수 부터 체크하기 시작
		unsigned long long pow = i * i;
		unsigned long long start = min / pow; //몇배수 부터 체크해야하는지 시작점을 잡기 위함
		//만약 MIN값이 6이면 시작점은 8이 될것이다(7은 제곱수가 아니므로) 그러기 위해서는 나머지가 있을때 
        //1을 더해주어야 한다 단순 몫으로 구하면 시작값 6보다 작은 4부터(4*1) 찾게된다
		if (min % pow != 0) 
			start++;
		for (unsigned long long j = start; pow * j <= max; ++j) {
			check[(pow * j) - min] = true;
		}
	}
	
	unsigned long long result = 0;
	for (unsigned long long i = 0; i < check.size(); ++i) {
		if (!check[i])
			result++;
	}
	std::cout << result;
	return 0;
}
 
 느낀점 
 - 에라토스테네스의 체 응용방법 
 - 기존 문제처럼 max값만큼 배열선언 시 메모리 초과 오류가 발생한다. 배열의 크기를 최소화할 수 있게    max-min을 해주어야 한다
 - max-min을 해주는 문제점 때문에 배열의 인덱스값을 실제 값과 동일하다고 볼 수 없다 -> 그러므로 시작점을 구하는 작업을 추가로 해주어야 한다.

Beakjoon] 제곱 ㄴㄴ 수 (백준 1016 코테) - 정수론 (C++)

댓글