백준 15649번 N과 M (1)

백준 15649번 N과 M (1) 문제이다.

문제는 다음과 같다.

문제만으로 규칙을 모르겠다면 입출력을 봐주자.

문제가 파악되었다면 문제를 풀어보자.

이번 문제는 백트래킹 문제이다. 

두번째 입력값인 m이 수열의 길이이기 때문에 이 값을 하나씩 증가시키며 모든 경우를 살펴보고 조건에 맞다면 출력하도록 짜준다.

언어는 C++을 이용하였다.

#include <iostream>

using namespace std;

int n, m;
int arr[8];
int arr2[8];
int check[8] = {0,};

void func(int cnt){
    if(cnt == m){
        for(int i = 0; i < m; i++){
            std::cout << arr[arr2[i]] << ' ';
        }
        std::cout << '\n';
    }

    for(int i = 0; i < n; i++){
        if(check[i] != 1){
            check[i] = 1;
            arr2[cnt] = i;
            func(cnt+1);
            check[i] = 0;
        }
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin >> n;
    std::cin >> m;
    for(int i = 0; i < n; i++){
        arr[i] = i + 1;
    }
    func(0);
}

가장 중요한것은 재귀 방식을 사용한다는 점이다. func내의 for문을 통해 모든 경우를 다 살펴볼 수 있다는 것이 키포인트가 될 것 같다.

 

성공!