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

안녕하세요 766님ㅎㅎ

죄송하지만 강의에서 설명하는 문제 외에는 답변을 드리지 않고 있습니다.

다만 제가 이 문제를 푼 코드는 다음과 같습니다.

참고부탁드립니다.

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<iostream> 

using namespace std;    
int N, R;  
int a[9], visited[9];
void go(int index, int n, int r){
    if(r == 0){
        for(int i = 0; i < R; i++){
            printf("%d ", a[i]);
        }
        printf("\n");
        return; 
    }

    for(int i = 1; i <= N; i++){
        if(visited[i]) continue;  
        a[index] = i;
        visited[i] = 1; 
        go(index + 1, n, r - 1); 
        visited[i] = 0; 
    }
    return;
}
int main(){
    scanf("%d %d", &N, &R);
    go(0, N, R);  
    return 0; 
}

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

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

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴이에요.

재귀를 이용한 순열 코드를 학습하면서 백준 15649번 N과 M(1) 문제를 해결하기 위해 교안의 코드를 사용하려고 하던데요, 순서가 오름차순으로 출력하기 위해서는 교안의 코드를 수정해야 할 것입니다.

교안의 코드를 한 번 살펴보면, Permutation 함수에서 매개변수로 순열의 시작 인덱스 idx와 마지막 인덱스 n이 들어가게 되는데요, 이때 시작 인덱스가 n일 경우 순열을 완성한 것으로 보고 출력하게 됩니다. 하지만 이렇게 작성된 코드는 순열의 오름차순이 보장되지 않습니다.

따라서, Permutation 함수 내에서 순서가 오름차순이 되도록 코드를 수정해야 합니다. 이를 위해서는 Permutation 함수 내에서 for문으로 배열을 돌 때, 시작 인덱스인 idx부터 n까지가 아니라, idx부터 n까지 출력할 때마다 idx 값을 1 증가시키는 방법을 이용하면 됩니다. 이렇게 수정된 코드를 실행하면, 오름차순으로 순열이 출력될 것입니다.

아래는 수정된 코드 예시입니다.

def Permutation(arr, idx, n):
    if idx == n:
        print(' '.join(map(str, arr)))
        return
    for i in range(idx, n):
        arr[i], arr[idx] = arr[idx], arr[i]
        Permutation(arr, idx+1, n)
        arr[i], arr[idx] = arr[idx], arr[i] # 원래대로 돌려놓기

N, M = map(int, input().split())
lst = [i+1 for i in range(N)]
Permutation(lst, 0, M)

이렇게 수정된 코드를 참고해 보시고, 문제를 해결해보세요! 좋은 결과 얻으시길 바랍니다.