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

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

15652번: N과 M (4)

백트래킹 C++

 

4는 2와 3을 합친 문제이다.

수열 내의 중복을 허용하고, 오름차순이다

 

2에서 사용했던 if문을 사용하고, 중복을 허용하기 때문에 반복여부를 체크하는 ischeck배열도 사용하지 않는다.

다만 중복을 허용하는 오름차순이기 때문에 for문 제어변수 i의 초기값을 result배열의 가장 최근 값부터 N까지로 한다.(<=, >=)

 

소스코드

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

#include <iostream>
using namespace std;
static int N, M;
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++){
                result[cnt] = i+1;
                f(cnt+1);
            }
        }
        else{
            for(int i = result[cnt-1]-1 ; i < N ; i++){
                result[cnt] = i+1;
                f(cnt+1);
            }
        }
    }
}

int main(){
    cin >> N >> M;
    int cnt = 0;
    f(cnt);
    return 0;
}