JArchive 프로그래밍 일기

N과 M문제집

1부터 12까지 시리즈가 있는 N과 M 문제집

순열, 조합을 연습하는 N과 M 시리즈 문제다. 백준님께서 1~4번 문제가 매우 중요하다고 하셨다.

문제

N과M(1) 백준 15649번

리뷰

재귀 호출을 이용해서 N개중에 M개를 고른다.

M개를 고를 때, permu() 함수는 매개변수로 지금 '몇 번째' 숫자를 고른다는 기준을 잡는다.

int check[ ] 배열을 이용해 특정 숫자를 골랐는지/안골랐는지 표시한다.

숫자 중복을 허용하지 않기 때문에 선택 여부 표시를 위해 필요하다.

코드

#include <iostream>
using namespace std;

int N, M;
int check[10]; // 확인 여부  
int answer[10]; // 선택한 인덱스  

void permu(int idx){ // 'idx' 번째에 어떤 수를 놓을지 고른다. 

    if(idx > M){ // 이미 M개를 골랐으니까, M번째를 초과하는 순간 종료. 

        // 수열 출력 
        for(int p = 1; p <= M; p++){
            cout << answer[p] << ' ';
        }
        cout << '\n';

        return; 
    }

    for(int i = 1; i <= N; i++){ 

        if(check[i]) continue; // 이미 선택된 수는 지나간다 

        check[i] = 1; // 선택 함
        answer[idx] = i; // idx 자리에 숫자 i 배치 

        permu(idx+1); // 다음 자리의 숫자 고르러 재귀          

        check[i] = 0; // 선택 안함  
    }
}

int main(void){

    freopen("input.txt", "rt", stdin);

    cin >> N >> M;

    permu(1);

    return 0;    
}

문제

N과M(2) 백준 15650번

백준님이 강조하셨다 중요하다고.

리뷰

오름차순 수열을 출력하되, 숫자가 중복되지 않도록 한다.

즉, 이미 고른 숫자보다 큰 숫자부터 골라야 한다.

코드 1

#include <iostream>
#include <algorithm> 
using namespace std;

// N과 M (2)  

int N, M;
bool check[10];
int answer[10];

void go(int index, int start){

    if(index == M){
        // 수열 출력 
        for(int i = 0; i < M; i++){
            cout << answer[i] << ' ';
        } 
        cout << '\n';
        return;
    }

    for(int i = start; i <= N; i++){
        if(check[i]) continue; // 이미 선택된 숫자라면 지나간다. 

        check[i] = true;
        answer[index] = i; // index 자리에 i를 선택한다. 
        go(index+1, i+1); // index+1 자리에 (==다음 자리)숫자를 고르기 위해 재귀 호출.
        check[i] = false; 
    }

}

int main(void){

     scanf("%d %d", &N, &M);

    go(0, 1); // 0번째를 채우자.  

    return 0;
} 

코드2

선택 한다/ 안한다의 관점

함수 시그니처는 아래와 같다.

void go(int num, int selected_cnt);

// num 에는 1부터 n까지의 숫자가 들어온다.  1, 2, 3, ... n 
// selected_cnt는 0부터 m-1까지 숫자가 들어온다. 

1부터 n까지 수가 들어오는데, 이 숫자를 선택 할지, 말지를 선택한다.

selected_cnt 가 m이 되는 순간 수열을 출력한다.

선택 한다면, selected_cnt 자리에 num을 넣는다.

arr[selected_cnt] = num; // 선택함  
go(num+1, selected_cnt+1);

arr[selected_cnt] = 0; // 선택 안함  
go(num+1, selected_cnt);

#include <iostream>
using namespace std;

// n과 m (2)

int n, m;
int arr[10]; // num 숫자를 선택 한다/안한다를 표시  

// num 에는 1부터 n까지의 숫자가 들어온다. 
// selected_cnt는 0부터 m-1까지 숫자가 들어온다. 

void go(int num, int selected_cnt){ // num 숫자를 선택 한다/안한다 ,  선택한 수의 개수 

    if(selected_cnt == m){
        // 수열 출력
        for(int i = 0; i < m; i++){
            printf("%d ", arr[i]);
        }
        cout << '\n';

        return; 
    } 

    if(num > n) return; // n을 초과하면 리턴  

    arr[selected_cnt] = num; // 선택함  
    go(num+1, selected_cnt+1);

    arr[selected_cnt] = 0; // 선택 안함  
    go(num+1, selected_cnt);

}

int main(void){

       scanf("%d %d", &n, &m);

      go(1, 0); 

    return 0;
}