Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
175 lines (164 sloc) 40.3 KB
---
layout : article
title: "[백준] 10972번 C/C++ 풀이 _ 다음 순열"
aside:
toc: true
tags: Algorithm
category : Algorithm
author: melonicedlatte
published : True
hellogohn_num : 319
key : 2018-08-05-223601
---
<h3>출처 :&nbsp;<a href="https://www.acmicpc.net/problem/10972">https://www.acmicpc.net/problem/10972</a>&nbsp;</h3><div class="col-md-12" style="background-color: transparent; border-radius: 0px; color: rgb(51, 51, 51); font-size: 13px; font-variant-numeric: normal; font-variant-east-asian: normal; width: 1170px;"><div class="page-header" style="border-radius: 0px;"><h1 style="border-radius: 0px; color: rgb(88, 95, 105); font-size: 28px; font-weight: 400; line-height: 35px; margin-top: 5px; text-shadow: none;"><span id="problem_title" style="border-radius: 0px;">다음 순열</span>
<span class="label label-success" style="border-radius: 0px; font-size: 11px; font-weight: 400; line-height: 11px; padding: 4px 7px;">성공</span>
<div class="btn-group pull-right problem-button" style="border-radius: 0px; display: block;">
<button class="btn btn-default" id="favorite_button" type="button" style="border-image: none 100% / 1 / 0 stretch; box-shadow: none; display: block; font-stretch: 100%; font-style: normal; font-variant: normal; font-weight: 400; line-height: 19.99px; outline-style: none; outline-width: 0px; padding: 6px 12px; text-transform: none;" data-favorite="0"><span class="glyphicon glyphicon-star-empty" id="favorite_image" style="border-radius: 0px; line-height: 14px;"></span></button>
</div>
</h1>
</div>
</div><div class="col-md-12" style="background-color: transparent; border-radius: 0px; color: rgb(51, 51, 51); font-size: 13px; font-variant-numeric: normal; font-variant-east-asian: normal; width: 1170px;">
<div class="table-responsive" style="border-radius: 0px;">
<table class="table" id="problem-info" style="border-radius: 0px; max-width: 1140px; width: 1140px;">
<thead style="border-radius: 0px;">
<tr style="border-radius: 0px;">
<th style="border-bottom: 0px none rgb(51, 51, 51); border-radius: 0px; border-top-color: rgb(51, 51, 51); border-top-style: none; line-height: 18.57px; width: 182.4px;">시간 제한</th>
<th style="border-bottom: 0px none rgb(51, 51, 51); border-radius: 0px; border-top-color: rgb(51, 51, 51); border-top-style: none; line-height: 18.57px; width: 182.4px;">메모리 제한</th>
<th style="border-bottom: 0px none rgb(51, 51, 51); border-radius: 0px; border-top-color: rgb(51, 51, 51); border-top-style: none; line-height: 18.57px; width: 193.8px;">제출</th>
<th style="border-bottom: 0px none rgb(51, 51, 51); border-radius: 0px; border-top-color: rgb(51, 51, 51); border-top-style: none; line-height: 18.57px; width: 193.8px;">정답</th>
<th style="border-bottom: 0px none rgb(51, 51, 51); border-radius: 0px; border-top-color: rgb(51, 51, 51); border-top-style: none; line-height: 18.57px; width: 193.8px;">맞은 사람</th>
<th style="border-bottom: 0px none rgb(51, 51, 51); border-radius: 0px; border-top-color: rgb(51, 51, 51); border-top-style: none; line-height: 18.57px; width: 193.8px;">정답 비율</th>
</tr>
</thead>
<tbody style="border-radius: 0px;">
<tr style="border-radius: 0px;">
<td style="border-radius: 0px; line-height: 18.57px;">1 초</td>
<td style="border-radius: 0px; line-height: 18.57px;">256 MB</td>
<td style="border-radius: 0px; line-height: 18.57px;">4396</td>
<td style="border-radius: 0px; line-height: 18.57px;">1941</td>
<td style="border-radius: 0px; line-height: 18.57px;">1489</td>
<td style="border-radius: 0px; line-height: 18.57px;">47.847%</td>
</tr>
</tbody>
</table>
</div>
</div><div id="problem-body" style="background-color: transparent; border-radius: 0px; color: rgb(51, 51, 51); font-size: 13px; font-variant-numeric: normal; font-variant-east-asian: normal;">
<div class="col-md-12" style="border-radius: 0px; width: 1170px;">
<section id="description" style="border-radius: 0px;">
<div class="headline" style="border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px; margin: 10px 0px 25px;">
<h2 style="border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px; color: rgb(88, 95, 105); display: inline-block; font-size: 22px; font-weight: 400; line-height: 33px; margin: 0px 0px -2px; padding-bottom: 5px; text-shadow: none;">문제</h2>
</div>
<div id="problem_description" style="border-radius: 0px; font-size: 16px; line-height: 30px;">
<p style="border-radius: 0px; color: rgb(85, 85, 85); margin-bottom: 10px; margin-top: 0px;">1부터 N까지의 수로 이루어진 순열이 있다. 이 때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.</p>
<p style="border-radius: 0px; color: rgb(85, 85, 85); margin-bottom: 10px; margin-top: 0px;">사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.</p>
<p style="border-radius: 0px; color: rgb(85, 85, 85); margin-bottom: 10px; margin-top: 0px;">N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.</p>
<ul style="border-radius: 0px;">
<li style="border-radius: 0px; color: rgb(85, 85, 85);">1, 2, 3</li>
<li style="border-radius: 0px; color: rgb(85, 85, 85);">1, 3, 2</li>
<li style="border-radius: 0px; color: rgb(85, 85, 85);">2, 1, 3</li>
<li style="border-radius: 0px; color: rgb(85, 85, 85);">2, 3, 1</li>
<li style="border-radius: 0px; color: rgb(85, 85, 85);">3, 1, 2</li>
<li style="border-radius: 0px; color: rgb(85, 85, 85);">3, 2, 1</li>
</ul>
</div>
</section>
</div>
<div class="col-md-12" style="border-radius: 0px; width: 1170px;">
<section id="input" style="border-radius: 0px;">
<div class="headline" style="border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px; margin: 10px 0px 25px;">
<h2 style="border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px; color: rgb(88, 95, 105); display: inline-block; font-size: 22px; font-weight: 400; line-height: 33px; margin: 0px 0px -2px; padding-bottom: 5px; text-shadow: none;">입력</h2>
</div>
<div id="problem_input" style="border-radius: 0px; font-size: 16px; line-height: 30px;">
<p style="border-radius: 0px; color: rgb(85, 85, 85); margin-bottom: 10px; margin-top: 0px;">첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.</p>
</div>
</section>
</div>
<div class="col-md-12" style="border-radius: 0px; width: 1170px;">
<section id="output" style="border-radius: 0px;">
<div class="headline" style="border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px; margin: 10px 0px 25px;">
<h2 style="border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px; color: rgb(88, 95, 105); display: inline-block; font-size: 22px; font-weight: 400; line-height: 33px; margin: 0px 0px -2px; padding-bottom: 5px; text-shadow: none;">출력</h2>
</div>
<div id="problem_output" style="border-radius: 0px; font-size: 16px; line-height: 30px;">
<p style="border-radius: 0px; color: rgb(85, 85, 85); margin-bottom: 10px; margin-top: 0px;">첫째&nbsp;줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.</p>
</div>
</section>
</div>
<div class="col-md-12" style="border-radius: 0px; width: 1170px;">
<div class="row" style="border-radius: 0px; clear: none;">
<div class="col-md-6" style="border-radius: 0px; width: 585px;">
<section id="sampleinput1" style="border-radius: 0px;">
<div class="headline" style="border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px; margin: 10px 0px 25px;">
<h2 style="border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px; color: rgb(88, 95, 105); display: inline-block; font-size: 22px; font-weight: 400; line-height: 33px; margin: 0px 0px -2px; padding-bottom: 5px; text-shadow: none;">예제 입력 1
<button class="btn btn-link copy-button" style="border-image: none 100% / 1 / 0 stretch; color: rgb(66, 139, 202); font-stretch: 100%; font-style: normal; font-variant: normal; font-weight: 400; line-height: 19.99px; outline-style: none; outline-width: 0px; padding: 0px; text-transform: none;" type="button" data-clipboard-target="#sample-input-1">복사</button>
</h2>
</div>
<pre class="sampledata" id="sample-input-1" style="background-color: rgb(247, 247, 249); border-color: rgb(225, 225, 232); border-radius: 0px; border-image: none 100% / 1 / 0 stretch; font-size: 18px; line-height: 25.71px; overflow-x: scroll; padding: 8px; word-break: normal; word-wrap: normal;">4
1 2 3 4
</pre>
</section>
</div>
<div class="col-md-6" style="border-radius: 0px; width: 585px;">
<section id="sampleoutput1" style="border-radius: 0px;">
<div class="headline" style="border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px; margin: 10px 0px 25px;">
<h2 style="border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px; color: rgb(88, 95, 105); display: inline-block; font-size: 22px; font-weight: 400; line-height: 33px; margin: 0px 0px -2px; padding-bottom: 5px; text-shadow: none;">예제 출력 1
<button class="btn btn-link copy-button" style="border-image: none 100% / 1 / 0 stretch; color: rgb(66, 139, 202); font-stretch: 100%; font-style: normal; font-variant: normal; font-weight: 400; line-height: 19.99px; outline-style: none; outline-width: 0px; padding: 0px; text-transform: none;" type="button" data-clipboard-target="#sample-output-1">복사</button>
</h2>
</div>
<pre class="sampledata" id="sample-output-1" style="background-color: rgb(247, 247, 249); border-color: rgb(225, 225, 232); border-radius: 0px; border-image: none 100% / 1 / 0 stretch; font-size: 18px; line-height: 25.71px; overflow-x: scroll; padding: 8px; word-break: normal; word-wrap: normal;">1 2 4 3
</pre>
</section>
</div>
</div>
</div>
<div class="col-md-12" style="border-radius: 0px; width: 1170px;">
<div class="row" style="border-radius: 0px; clear: none;">
<div class="col-md-6" style="border-radius: 0px; width: 585px;">
<section id="sampleinput2" style="border-radius: 0px;">
<div class="headline" style="border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px; margin: 10px 0px 25px;">
<h2 style="border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px; color: rgb(88, 95, 105); display: inline-block; font-size: 22px; font-weight: 400; line-height: 33px; margin: 0px 0px -2px; padding-bottom: 5px; text-shadow: none;">예제 입력 2
<button class="btn btn-link copy-button" style="border-image: none 100% / 1 / 0 stretch; color: rgb(66, 139, 202); font-stretch: 100%; font-style: normal; font-variant: normal; font-weight: 400; line-height: 19.99px; outline-style: none; outline-width: 0px; padding: 0px; text-transform: none;" type="button" data-clipboard-target="#sample-input-2">복사</button>
</h2>
</div>
<pre class="sampledata" id="sample-input-2" style="background-color: rgb(247, 247, 249); border-color: rgb(225, 225, 232); border-radius: 0px; border-image: none 100% / 1 / 0 stretch; font-size: 18px; line-height: 25.71px; overflow-x: scroll; padding: 8px; word-break: normal; word-wrap: normal;">5
5 4 3 2 1
</pre>
</section>
</div>
<div class="col-md-6" style="border-radius: 0px; width: 585px;">
<section id="sampleoutput2" style="border-radius: 0px;">
<div class="headline" style="border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px; margin: 10px 0px 25px;">
<h2 style="border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px; color: rgb(88, 95, 105); display: inline-block; font-size: 22px; font-weight: 400; line-height: 33px; margin: 0px 0px -2px; padding-bottom: 5px; text-shadow: none;">예제 출력 2
<button class="btn btn-link copy-button" style="border-image: none 100% / 1 / 0 stretch; color: rgb(66, 139, 202); font-stretch: 100%; font-style: normal; font-variant: normal; font-weight: 400; line-height: 19.99px; outline-style: none; outline-width: 0px; padding: 0px; text-transform: none;" type="button" data-clipboard-target="#sample-output-2">복사</button>
</h2>
</div>
<pre class="sampledata" id="sample-output-2" style="background-color: rgb(247, 247, 249); border-color: rgb(225, 225, 232); border-radius: 0px; border-image: none 100% / 1 / 0 stretch; font-size: 18px; line-height: 25.71px; overflow-x: scroll; padding: 8px; word-break: normal; word-wrap: normal;">-1
</pre>
</section>
</div>
</div>
</div>
<div class="col-md-12" style="border-radius: 0px; width: 1170px;">
</div>
</div><div class="col-md-12" style="background-color: transparent; border-radius: 0px; color: rgb(51, 51, 51); font-size: 13px; font-variant-numeric: normal; font-variant-east-asian: normal; width: 1170px;">
<section id="source" style="border-radius: 0px;">
<div class="headline" style="border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px; margin: 10px 0px 25px;">
<h2 style="border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px; color: rgb(88, 95, 105); display: inline-block; font-size: 22px; font-weight: 400; line-height: 33px; margin: 0px 0px -2px; padding-bottom: 5px; text-shadow: none;">출처</h2>
</div>
<ul style="border-radius: 0px;">
<li style="border-radius: 0px; color: rgb(85, 85, 85);">문제를 만든 사람:
<a href="https://www.acmicpc.net/user/baekjoon" style="background-attachment: scroll; background-clip: border-box; background-image: none; background-origin: padding-box; background-position: 0px 0px; background-repeat: repeat; background-size: auto; border-radius: 0px; color: rgb(85, 85, 85); outline-style: none; outline-width: 0px;">baekjoon</a>
</li>
</ul>
</section>
</div><p><span style="background-color: transparent; color: rgb(51, 51, 51); font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-size: 13px; font-variant-numeric: normal; font-variant-east-asian: normal;">
</span><span style="background-color: transparent; color: rgb(51, 51, 51); font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-size: 13px; font-variant-numeric: normal; font-variant-east-asian: normal;">
</span><span style="background-color: transparent; color: rgb(51, 51, 51); font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-size: 13px; font-variant-numeric: normal; font-variant-east-asian: normal;">
</span><span style="background-color: transparent; color: rgb(51, 51, 51); font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-size: 13px; font-variant-numeric: normal; font-variant-east-asian: normal;">
</span></p><div class="col-md-12" style="background-color: transparent; border-radius: 0px; color: rgb(51, 51, 51); font-size: 13px; font-variant-numeric: normal; font-variant-east-asian: normal; width: 1170px;">
<section id="problem_tags" style="border-radius: 0px;">
<div class="headline" style="border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px; margin: 10px 0px 25px;">
<h2 style="border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px; color: rgb(88, 95, 105); display: inline-block; font-size: 22px; font-weight: 400; line-height: 33px; margin: 0px 0px -2px; padding-bottom: 5px; text-shadow: none;">알고리즘 분류</h2>
</div>
<ul class="spoiler-list" style="border-radius: 0px;">
<li style="border-radius: 0px; color: rgb(85, 85, 85);">
<a class="spoiler-link" href="https://www.acmicpc.net/problem/tag/%EC%88%9C%EC%97%B4" style="background-attachment: scroll; background-clip: border-box; background-image: none; background-origin: padding-box; background-position: 0px 0px; background-repeat: repeat; background-size: auto; border-radius: 0px; color: rgb(85, 85, 85); outline-style: none; outline-width: 0px;">순열</a></li></ul></section></div><p><span style="color: inherit; font-family: &quot;Jeju Gothic&quot;, &quot;Nanum Gothic Coding&quot;, &quot;KoPub Batang&quot;, &quot;Nanum Gothic&quot;, serif; font-size: 24px; font-weight: 800;">풀이</span><br></p><p style="line-height: 27px; color: rgb(51, 51, 51); font-variant-numeric: normal; font-variant-east-asian: normal; background: none 0% 0% / auto repeat scroll padding-box border-box transparent; text-shadow: none;">이번 문제의 풀이에는 '재귀함수'를 사용했다. (풀고 나니 끝에서 부터 찾으면 재귀함수 필요 없을 것 같다. )</p><p style="line-height: 27px; font-variant-numeric: normal; font-variant-east-asian: normal; background: none 0% 0% / auto repeat scroll padding-box border-box transparent; text-shadow: none;"><font color="#333333">다음 문제인 '이전 수열'을 먼저 풀고 와서 더 쉽게 풀었다.&nbsp;</font><a href="http://hellogohn.com/post_one318">http://hellogohn.com/post_one318</a><a href="http://hellogohn.com/post_one318"></a>&nbsp;링크에서 확인할 수 있다.&nbsp;<br><br></p><p style="line-height: 27px; color: rgb(51, 51, 51); font-variant-numeric: normal; font-variant-east-asian: normal; background: none 0% 0% / auto repeat scroll padding-box border-box transparent; text-shadow: none;"><br></p><p><img src="/system/uploads/images/000/001/439/original/image.png?1533475717" style="width: 50%;"><br></p><p style="line-height: 27px; color: rgb(51, 51, 51); font-variant-numeric: normal; font-variant-east-asian: normal; background: none 0% 0% / auto repeat scroll padding-box border-box transparent; text-shadow: none;">주어진 수열에서 숫자가 증가하는 부분을 탐색한다.&nbsp;<br><span style="background-color: transparent;">해당 부분은 다음 수열이 될 때 '바뀔 수 있는 부분' 이다.&nbsp;</span></p><p style="line-height: 27px; color: rgb(51, 51, 51); font-variant-numeric: normal; font-variant-east-asian: normal; background: none 0% 0% / auto repeat scroll padding-box border-box transparent; text-shadow: none;">해당 부분을 찾았다면 a<span style="position: relative; font-size: 13.5px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">k+1&nbsp;</span><span style="background-color: transparent;">부분부터 끝까지 탐색하여 다시 요소 중에 왼쪽 요소가 오른쪽 요소보다 더 작은 구간을 찾는다.&nbsp;</span></p><div><span style="background-color: transparent;"><br></span></div><p><img src="/system/uploads/images/000/001/440/original/image.png?1533475972" style="width: 713.546px; height: 198.135px;"><br></p><p style="line-height: 27px; color: rgb(51, 51, 51); font-variant-numeric: normal; font-variant-east-asian: normal; background: none 0% 0% / auto repeat scroll padding-box border-box transparent; text-shadow: none;">예를 들어, 현재의 수열이 위와 같다고 생각해보자.&nbsp;<br>위에서 찾은 가장 우측의&nbsp; a<span style="position: relative; font-size: 13.5px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">t-1&nbsp;</span>&lt;<span style="background-color: transparent;">&nbsp;</span>a<span style="position: relative; font-size: 13.5px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">t&nbsp;</span><span style="background-color: transparent;">&nbsp;인 위치는 12가 위치한 인덱스이다.&nbsp;</span></p><p style="line-height: 27px; color: rgb(51, 51, 51); font-variant-numeric: normal; font-variant-east-asian: normal; background: none 0% 0% / auto repeat scroll padding-box border-box transparent; text-shadow: none;">이 경우에 t-1 이전의 모든 인덱스 들은 값이 변하지 않는다.&nbsp;<br>[t-1 , n] 사이의 값을 변경해주면 이전 수열을 구할 수 있다.&nbsp;</p><p style="line-height: 27px; color: rgb(51, 51, 51); font-variant-numeric: normal; font-variant-east-asian: normal; background: none 0% 0% / auto repeat scroll padding-box border-box transparent; text-shadow: none;">변경하는 방법은 5보다 큰 바로 다음 수를 선택하여 지금 5의 위치에 넣고, 나머지는 오름차순으로 넣어주는 것이다.&nbsp;<br><span style="background-color: transparent;">여기에서는 5보다 큰 9를 선택하여 5의 자리를 넣고 5를 포함한 나머지 숫자를 오름차순으로 정렬하여 배열에 넣어준다.&nbsp;</span></p><p style="line-height: 27px; color: rgb(51, 51, 51); font-variant-numeric: normal; font-variant-east-asian: normal; background: none 0% 0% / auto repeat scroll padding-box border-box transparent; text-shadow: none;">이 문제에서는 재귀로 구현하는 것이 for문으로 구현하는 것 보다 훨씬 어렵고 귀찮은 작업 같다.&nbsp;</p><div><br></div><h3>소스코드</h3><div class="colorscripter-code" style="color:#f0f0f0; font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace !important; position:relative !important; overflow:auto"><table class="colorscripter-code-table" style="margin:0; padding:0; border:none; background-color:#272727; border-radius:4px;" cellspacing="0" cellpadding="0"><tbody><tr><td style="padding:6px; border-right:2px solid #4f4f4f"><div style="margin: 0px; padding: 0px; word-break: normal; text-align: right; color: rgb(170, 170, 170); line-height: 130%;"><div style="line-height:130%">1</div><div style="line-height:130%">2</div><div style="line-height:130%">3</div><div style="line-height:130%">4</div><div style="line-height:130%">5</div><div style="line-height:130%">6</div><div style="line-height:130%">7</div><div style="line-height:130%">8</div><div style="line-height:130%">9</div><div style="line-height:130%">10</div><div style="line-height:130%">11</div><div style="line-height:130%">12</div><div style="line-height:130%">13</div><div style="line-height:130%">14</div><div style="line-height:130%">15</div><div style="line-height:130%">16</div><div style="line-height:130%">17</div><div style="line-height:130%">18</div><div style="line-height:130%">19</div><div style="line-height:130%">20</div><div style="line-height:130%">21</div><div style="line-height:130%">22</div><div style="line-height:130%">23</div><div style="line-height:130%">24</div><div style="line-height:130%">25</div><div style="line-height:130%">26</div><div style="line-height:130%">27</div><div style="line-height:130%">28</div><div style="line-height:130%">29</div><div style="line-height:130%">30</div><div style="line-height:130%">31</div><div style="line-height:130%">32</div><div style="line-height:130%">33</div><div style="line-height:130%">34</div><div style="line-height:130%">35</div><div style="line-height:130%">36</div><div style="line-height:130%">37</div><div style="line-height:130%">38</div><div style="line-height:130%">39</div><div style="line-height:130%">40</div><div style="line-height:130%">41</div><div style="line-height:130%">42</div><div style="line-height:130%">43</div><div style="line-height:130%">44</div><div style="line-height:130%">45</div><div style="line-height:130%">46</div><div style="line-height:130%">47</div><div style="line-height:130%">48</div><div style="line-height:130%">49</div><div style="line-height:130%">50</div><div style="line-height:130%">51</div><div style="line-height:130%">52</div><div style="line-height:130%">53</div><div style="line-height:130%">54</div><div style="line-height:130%">55</div><div style="line-height:130%">56</div><div style="line-height:130%">57</div><div style="line-height:130%">58</div><div style="line-height:130%">59</div><div style="line-height:130%">60</div><div style="line-height:130%">61</div><div style="line-height:130%">62</div><div style="line-height:130%">63</div><div style="line-height:130%">64</div><div style="line-height:130%">65</div><div style="line-height:130%">66</div><div style="line-height:130%">67</div></div></td><td style="padding-top: 6px; padding-bottom: 6px;"><div style="margin: 0px; padding: 0px; line-height: 130%;"><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#0086b3">#include</span>&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&lt;</span>iostream<span style="color:#aaffaa"></span><span style="color:#ff3399">&gt;</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#0086b3">#include</span>&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&lt;</span><span style="color:#4be6fa">vector</span><span style="color:#ff3399">&gt;</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#0086b3">#include</span>&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&lt;</span>algorithm<span style="color:#aaffaa"></span><span style="color:#ff3399">&gt;</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#0086b3">#include</span>&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&lt;</span>functional<span style="color:#aaffaa"></span><span style="color:#ff3399">&gt;</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#0086b3">#pragma</span>&nbsp;warning(disable&nbsp;:&nbsp;<span style="color:#c10aff">4996</span>)</div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#ff3399">using</span>&nbsp;<span style="color:#ff3399">namespace</span>&nbsp;<span style="color:#4be6fa">std</span>;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#4be6fa">int</span>&nbsp;N;</div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#4be6fa">vector</span><span style="color:#ff3399">&lt;</span><span style="color:#4be6fa">int</span><span style="color:#ff3399">&gt;</span>&nbsp;num_vec;</div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#4be6fa">vector</span><span style="color:#ff3399">&lt;</span><span style="color:#4be6fa">int</span><span style="color:#ff3399">&gt;</span>&nbsp;answer_vec;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#4be6fa">int</span>&nbsp;is_find_next(<span style="color:#4be6fa">int</span>&nbsp;start,&nbsp;<span style="color:#4be6fa">int</span>&nbsp;<span style="color:#4be6fa">end</span>)&nbsp;{</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#4be6fa">int</span>&nbsp;sear_idx;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">for</span>&nbsp;(sear_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;start;&nbsp;sear_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&lt;</span>&nbsp;<span style="color:#4be6fa">end</span>;&nbsp;sear_idx<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>)&nbsp;{</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">if</span>&nbsp;(num_vec.at(sear_idx)&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&gt;</span>&nbsp;num_vec.at(sear_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>&nbsp;<span style="color:#c10aff">1</span>))</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer_vec.at(sear_idx)&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;num_vec.at(sear_idx);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">else</span>&nbsp;<span style="color:#ff3399">break</span>;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;}</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">if</span>&nbsp;(sear_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&gt;</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;<span style="color:#4be6fa">end</span>)&nbsp;<span style="color:#ff3399">return</span>&nbsp;<span style="color:#c10aff">0</span>;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#999999">//&nbsp;we&nbsp;find&nbsp;descend&nbsp;sector</span></div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#4be6fa">int</span>&nbsp;is_find_before_flag&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;is_find_next(sear_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>&nbsp;<span style="color:#c10aff">1</span>,&nbsp;<span style="color:#4be6fa">end</span>);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#999999">//&nbsp;there&nbsp;is&nbsp;no&nbsp;any&nbsp;descend&nbsp;sector</span></div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">if</span>&nbsp;(is_find_before_flag&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;<span style="color:#c10aff">0</span>)&nbsp;{</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#999999">//&nbsp;한&nbsp;칸&nbsp;큰&nbsp;놈을&nbsp;현재&nbsp;위치에&nbsp;넣어주고&nbsp;나머지는&nbsp;오름차순으로&nbsp;정렬해서&nbsp;하나씩&nbsp;넣어준다.&nbsp;</span></div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sort(num_vec.<span style="color:#4be6fa">begin</span>()&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>&nbsp;sear_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>&nbsp;<span style="color:#c10aff">1</span>,&nbsp;num_vec.<span style="color:#4be6fa">end</span>());</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#999999">//&nbsp;현재&nbsp;인덱스&nbsp;보다&nbsp;한&nbsp;칸&nbsp;큰&nbsp;놈을&nbsp;선택&nbsp;</span></div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">auto</span>&nbsp;_iter&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;upper_bound(num_vec.<span style="color:#4be6fa">begin</span>()&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>&nbsp;sear_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>&nbsp;<span style="color:#c10aff">1</span>&nbsp;,&nbsp;num_vec.<span style="color:#4be6fa">end</span>(),&nbsp;num_vec.at(sear_idx));</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#4be6fa">int</span>&nbsp;one_big_index&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;_iter&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">-</span>&nbsp;num_vec.<span style="color:#4be6fa">begin</span>();</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#4be6fa">int</span>&nbsp;one_big_value&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;num_vec.at(one_big_index);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer_vec.at(sear_idx)&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;num_vec.at(one_big_index);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">for</span>&nbsp;(<span style="color:#4be6fa">int</span>&nbsp;new_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;sear_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>&nbsp;<span style="color:#c10aff">1</span>;&nbsp;new_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&lt;</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;<span style="color:#4be6fa">end</span>;&nbsp;new_idx<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>)</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">if</span>&nbsp;(one_big_value&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;num_vec.at(new_idx))</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer_vec.at(new_idx)&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;num_vec.at(sear_idx);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">else</span></div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer_vec.at(new_idx)&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;num_vec.at(new_idx);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;}</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">return</span>&nbsp;<span style="color:#c10aff">1</span>;</div><div style="padding:0 6px; white-space:pre; line-height:130%">}</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#4be6fa">int</span>&nbsp;main()&nbsp;{</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#4be6fa">scanf</span>(<span style="color:#ffd500">"%d"</span>,&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&amp;</span>N);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;num_vec.resize(N,&nbsp;<span style="color:#c10aff">0</span>);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;answer_vec.resize(N,&nbsp;<span style="color:#c10aff">0</span>);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">for</span>&nbsp;(<span style="color:#4be6fa">int</span>&nbsp;n_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;<span style="color:#c10aff">0</span>;&nbsp;n_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&lt;</span>&nbsp;N;&nbsp;n_idx<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>)</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#4be6fa">scanf</span>(<span style="color:#ffd500">"%d"</span>,&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&amp;</span>num_vec.at(n_idx));</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#4be6fa">int</span>&nbsp;is_get_answer&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;is_find_next(<span style="color:#c10aff">0</span>,&nbsp;N&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">-</span>&nbsp;<span style="color:#c10aff">1</span>);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">if</span>&nbsp;(<span style="color:#aaffaa"></span><span style="color:#ff3399">!</span>is_get_answer)&nbsp;{</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#4be6fa">printf</span>(<span style="color:#ffd500">"-1"</span>);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">return</span>&nbsp;<span style="color:#c10aff">0</span>;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;}</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">for</span>&nbsp;(<span style="color:#4be6fa">int</span>&nbsp;n_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span>&nbsp;<span style="color:#c10aff">0</span>;&nbsp;n_idx&nbsp;<span style="color:#aaffaa"></span><span style="color:#ff3399">&lt;</span>&nbsp;N;&nbsp;n_idx<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>)</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#4be6fa">printf</span>(<span style="color:#ffd500">"%d&nbsp;"</span>,&nbsp;answer_vec.at(n_idx)&nbsp;?&nbsp;answer_vec.at(n_idx)&nbsp;:&nbsp;num_vec.at(n_idx));</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff3399">return</span>&nbsp;<span style="color:#c10aff">0</span>;</div><div style="padding:0 6px; white-space:pre; line-height:130%">}</div></div><div style="text-align:right; margin-top:-13px; margin-right:5px; font-size:9px; font-style:italic"><a href="http://colorscripter.com/info#e" target="_blank" style="color: rgb(79, 79, 79);">Colored by Color Scripter</a></div></td><td style="vertical-align: bottom; padding-right: 2px; padding-bottom: 4px;"><a href="http://colorscripter.com/info#e" target="_blank" style="color: white;"><span style="font-size: 9px; word-break: normal; background-color: rgb(79, 79, 79); border-radius: 10px; padding: 1px;">cs</span></a></td></tr></tbody></table></div>
You can’t perform that action at this time.