JArchive 프로그래밍 일기

문제

N과M(5) 백준 15654번

리뷰

1부터 N까지의 자연수가 아니라, 입력받은 N개의 수열을 이용한다.

중복을 허용하지 않고 2개 고르는 것이라서 중복체크를 위해 ch [10] 배열이 필요하다.

수열은 사전 순으로 증가하는 순으로 출력해야 하니까, 입력받자마자 sort() 했다.

코드

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

// n과 m  (5)

int N, M; // 1부터 N까지의 자연수 중에서 M개를 고른 수열.  
int arr[10]; // 입력받은 수열 저장.
int ch[10]; // 중복을 허용하지 않으니까, 체크 배열이 필요하다.
int answer[10];

void go(int index){

    if(index == M){
        for(int i = 0; i < M; i++){
            printf("%d ", answer[i]);
        }
        cout << '\n';
        return;
    }

    for(int i = 0; i < N; i++){
        if(ch[i]) continue;

        ch[i] = 1;
        answer[index] = arr[i];
        go(index+1);
        ch[i] = 0;
    }
}

int main(void){

    cin >> N >> M;

     for(int i = 0; i < N; i++){
         scanf("%d", &arr[i]);
    }

    sort(arr, arr+N);

     go(0);

    return 0;
}

문제

N과M(6) 백준 15655번

리뷰

수열의 중복을 허용하지 않고, 사전 순으로 증가하는 순서로 출력해야 한다.

수열은 오름차순이어야 하므로 go 함수에 start 변수를 넣어서 이전 인덱스 보다 큰 인덱스부터 수열의 숫자를 고르도록 했다.

코드

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

// n과 m  (6)
// 중복 허용 안 함. 오름차순 수열.

int N, M; // 1부터 N까지의 자연수 중에서 M개를 고른 수열.  
int arr[10];
int ch[10];
int answer[10];

void go(int index, int start){

    if(index == M){
        for(int i = 0; i < M; i++){
            printf("%d ", answer[i]);
        }
        cout << '\n';
        return;
    }

    for(int i = start; i < N; i++){
        if(ch[i]) continue;

        ch[i] = 1;
        answer[index] = arr[i];
        go(index+1, i+1);
        ch[i] = 0;
    }
}

int main(void){

    cin >> N >> M;

     for(int i = 0; i < N; i++){
         scanf("%d", &arr[i]);
    }

    sort(arr, arr+N);

     go(0, 0);

    return 0;
}