인프런 커뮤니티 질문&답변

cse.ict.1님의 프로필 이미지
cse.ict.1

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

1-A

1-A 일곱 난쟁이 next_permutation 코드 관련 질문드립니다

작성

·

176

0

안녕하세요:)

일곱난쟁이 문제에서 "결과값을 오름차순으로 출력" 해야하는 부분과 관련하여 문의드립니다.

next_permutation을 활용하여 경우의 수를 뽑는 경우에, 앞에서 부터 7개 순열을 잘라서 보면 어떤 것은 오름차순으로 되어있지 않은데 혹시 만일 그러한 순열이 답이 되는 경우 sort로 정렬을 다시 안해줘도 되나요?

예를 들어, 본 문제 테스트케이스의 경우[ 7 8 10 13 19 20 23] 이라는 값이 딱 sum이 100인 경우여서 오름차순 그대로 값이 출력이 되지만.. 만약 [7 8 10 13 15 25 19] 가 답이었다고 가정한다면 .. 오름차순이 안되는게 아닌지 해서요!

 

감사합니다:)

 

답변 1

0

큰돌님의 프로필 이미지
큰돌
지식공유자

안녕하세요 ㅎㅎ

next_permutation을 활용하여 경우의 수를 뽑는 경우에, 앞에서 부터 7개 순열을 잘라서 보면 어떤 것은 오름차순으로 되어있지 않은데 혹시 만일 그러한 순열이 답이 되는 경우 sort로 정렬을 다시 안해줘도 되나요?

>> 순열을 사용할 경우 >> sort 이후에 next_permutation 사용 >> 이 경우 오름차순이 이미 되어있습니다.

무조건

sort 이후에 next_permutation 사용

이렇게 사용하셔야 합니다.

해당부분은 0주차 : permutation 강의에서도 알려드리고 있습니다.

 

예를 들어, 본 문제 테스트케이스의 경우[ 7 8 10 13 19 20 23] 이라는 값이 딱 sum이 100인 경우여서 오름차순 그대로 값이 출력이 되지만.. 만약 [7 8 10 13 15 25 19] 가 답이었다고 가정한다면 .. 오름차순이 안되는게 아닌지 해서요!

>>

아마 이 입력의 경우겠죠?

7 8 10 13 15 25 19 100 100

 

#include <bits/stdc++.h>
using namespace std;  
int a[9]; 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for(int i = 0; i < 9; i++){
        cin >> a[i]; 
    }
    sort(a, a + 9);
    do{
        int sum = 0; 
        for(int i = 0; i < 7; i++) sum += a[i]; 
        if(sum == 100)break;
    }while(next_permutation(a, a + 9)); 
    for(int i = 0; i < 7; i++) cout << a[i] << "\n"; 
    return 0;
}

넣어보시면 오름차순으로 잘 출력이 되는 것을 볼 수 있습니다.

 

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

cse.ict.1님의 프로필 이미지
cse.ict.1

작성한 질문수

질문하기