[백준 15650] 알고리즘 18일차 : N과 M(2)

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

백트래킹 c++

N과 M(1) 문제의 연장선이다.

1은 순열이었고 2는 오름차순이라는 조건을 줘서 조합이다.

그래서 반복문을 0부터 N-1까지가 아니라

result 배열의 가장 최근의 수 부터 N-1까지 반복한다. (실제로 입력하는 수는 배열의 가장 최근의 수 보다 크고, N보다 작거나 같은 수이다. )

이때 cnt가 0인 경우는 따로 처리해준다. result[-1]ㄸㅐ문

더 좋은 방법이 있을 수 있겠지만 일단..

 

소스코드

//
//  15650.cpp
//  back tracking
//
//  Created by 임수정 on 2020/07/08.
//  Copyright © 2020 임수정. All rights reserved.
//

#include <iostream>
using namespace std;
static int N, M;
bool ischeck[8] = {false,};
int result[8];

void f(int cnt){
    if(cnt == M){
        for(int i = 0 ; i < M ; i++)
            cout << result[i] << " ";
        cout << "\n";
    }
    else{
        if(cnt == 0){
            for(int i = 0 ; i < N ; i++){
                if(!ischeck[i]){
                    ischeck[i] = true;
                    result[cnt] = i+1;
                    f(cnt+1);
                    ischeck[i] = false;
                }
            }
        }
        else{
            for(int i = result[cnt-1] ; i < N ; i++){
                if(!ischeck[i]){
                    ischeck[i] = true;
                    result[cnt] = i+1;
                    f(cnt+1);
                    ischeck[i] = false;
                }
            }
        }
    }
}