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


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

			

			

			

			<div>
				

				            
                
	
	
		<div>
			<p>운동하는 개발자/알고리즘, 코딩테스트</p>
			
			<p>
				<span>2023. 12. 14. 21:48</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/1744" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/1744</a></span></h3>
<figure id="og_1702557255724" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="1744번: 수 묶기" data-og-description="길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/1744" data-og-url="https://www.acmicpc.net/problem/1744" data-og-image="https://scrap.kakaocdn.net/dn/rzkOQ/hyUL0Ycm7d/mgKNln0LxLxZKDYRc8NDlk/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"><a href="https://www.acmicpc.net/problem/1744" target="_blank" rel="noopener" data-source-url="https://www.acmicpc.net/problem/1744">

<div>
<p data-ke-size="size16">1744번: 수 묶기</p>
<p data-ke-size="size16">길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에</p>
<p data-ke-size="size16">www.acmicpc.net</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/rzkOQ/hyUL0Ycm7d/mgKNln0LxLxZKDYRc8NDlk/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="992" data-origin-height="333"><span data-url="https://blog.kakaocdn.net/dn/bbvpBB/btsBVALTXzP/y8NHhkQdX5oBOLkSHWg4zK/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/bbvpBB/btsBVALTXzP/y8NHhkQdX5oBOLkSHWg4zK/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="992" data-origin-height="333"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 최댓값을 구하기 위해 공식을 잘 살펴보면 양/음 수끼리 절댓값이 큰 수의 곱을 묶어줘야 하며<br>&nbsp;0은 절대로 곱해져서는 안되며 양수 1은 곱해 봤자 이므로 더해줘야 한다.<br>&nbsp;- 위의 분석으로 숫자는 4개의 타입을 가진다 (0, 1, 1을 제외한 양수, 음수)<br>&nbsp;- <span>1을 제외한 양수와 음수는</span> 우선순위 큐로 나눠서 정렬시키고 남은 수가 1개 이하가 될 때까지 곱을 묶어준다<br>&nbsp;- <u>마지막 음수에 -1이 남는경우 0이 있는지 체크하여 0과 곱해줘서 없애준다<br></u>&nbsp;- 정렬시 음수는 작은 순부터 정렬시켜야 한다. (절댓값이 커야 하므로)</p>
<p data-ke-size="size16">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+ 이 악마같은 예제는 음수가 하나뿐이라 이 정렬을 잘못해도 모든 예제를 통과해 버린다.<u></u></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;queue&gt;
#include &lt;vector&gt;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	int N;
	std::cin &gt;&gt; N;

	std::priority_queue&lt;int, std::vector&lt;int&gt;, std::less&lt;int&gt;&gt; plus;
	std::priority_queue&lt;int, std::vector&lt;int&gt;, std::greater&lt;int&gt;&gt; minus;
	int zero_cnt = 0;
	int one_cnt = 0;

	for (int i = 0; i &lt; N; ++i) {
		int temp;
		std::cin &gt;&gt; temp;
		if (temp &gt; 1) {
			plus.push(temp);
		}
		else if (temp == 0)
			++zero_cnt;
		else if (temp == 1)
			++one_cnt;
		else {
			minus.push(temp);
		}
	}

	int result = one_cnt;

	while (plus.size() &gt; 1) {
		int first = plus.top();
		plus.pop();
		int second = plus.top();
		plus.pop();
		result += first * second;
	}
	if (!plus.empty()) {
		result += plus.top();
	}

	while (minus.size() &gt; 1) {
		int first = minus.top();
		minus.pop();
		int second = minus.top();
		minus.pop();
		result += first * second;
	}
	if (!minus.empty()) {
		if (zero_cnt &gt; 0) {
			zero_cnt--;
		}
		else
			result += minus.top();		
	}

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

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

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 우선순위 큐의 사용 숙련도 상승<br>&nbsp;- 그리디 알고리즘은 특정 스킬을 공식화해서 풀기보다는 문제를 정확히 이해하고 조건을 찾아낼 수 있어야 한다.</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/1744
 
 문제 
 
 
 풀이 
 - 최댓값을 구하기 위해 공식을 잘 살펴보면 양/음 수끼리 절댓값이 큰 수의 곱을 묶어줘야 하며
 0은 절대로 곱해져서는 안되며 양수 1은 곱해 봤자 이므로 더해줘야 한다.
 - 위의 분석으로 숫자는 4개의 타입을 가진다 (0, 1, 1을 제외한 양수, 음수)
 - 1을 제외한 양수와 음수는 우선순위 큐로 나눠서 정렬시키고 남은 수가 1개 이하가 될 때까지 곱을 묶어준다
 - 마지막 음수에 -1이 남는경우 0이 있는지 체크하여 0과 곱해줘서 없애준다
 - 정렬시 음수는 작은 순부터 정렬시켜야 한다. (절댓값이 커야 하므로)
         + 이 악마같은 예제는 음수가 하나뿐이라 이 정렬을 잘못해도 모든 예제를 통과해 버린다.
 
☕코드는 아래 숨김
더보기
#include <iostream>
#include <queue>
#include <vector>
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int N;
	std::cin >> N;
	std::priority_queue<int, std::vector<int>, std::less<int>> plus;
	std::priority_queue<int, std::vector<int>, std::greater<int>> minus;
	int zero_cnt = 0;
	int one_cnt = 0;
	for (int i = 0; i < N; ++i) {
		int temp;
		std::cin >> temp;
		if (temp > 1) {
			plus.push(temp);
		}
		else if (temp == 0)
			++zero_cnt;
		else if (temp == 1)
			++one_cnt;
		else {
			minus.push(temp);
		}
	}
	int result = one_cnt;
	while (plus.size() > 1) {
		int first = plus.top();
		plus.pop();
		int second = plus.top();
		plus.pop();
		result += first * second;
	}
	if (!plus.empty()) {
		result += plus.top();
	}
	while (minus.size() > 1) {
		int first = minus.top();
		minus.pop();
		int second = minus.top();
		minus.pop();
		result += first * second;
	}
	if (!minus.empty()) {
		if (zero_cnt > 0) {
			zero_cnt--;
		}
		else
			result += minus.top();		
	}
	std::cout << result;
	
	return 0;
}
 
 알게 된 것 
 - 우선순위 큐의 사용 숙련도 상승
 - 그리디 알고리즘은 특정 스킬을 공식화해서 풀기보다는 문제를 정확히 이해하고 조건을 찾아낼 수 있어야 한다.

Beakjoon] 수 묶기 (백준 1744 코테) - 그리디

댓글