백준 15649 C++

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

15649번: N과 M (1)

 

정답 코드

#include <iostream>
using namespace std;

int N, M;
int arr[9];
bool visited[9];

void dfs(int k){
    if (k == M){
        for (int i = 0; i < M; i++){
            cout << arr[i]<< ' ';
        }
        cout << '\n'; 
    }
    else{
        for (int i = 0; i < N; i++){
            if (!visited[i]){ // 방문할 노드(인덱스)가 있으면
                visited[i] = true; // 방문 체크해줌
                arr[k] = i+1;
                dfs(k + 1); // 다음 노드(인덱스) 재귀 고고 = 더 깊이 들어간다는 소리
                visited[i] = false; // 초기화 과정 (백트래킹)
            }
        }
    }
}

int main(){
    cin >> N >> M;
    dfs(0);
}

visited 배열은 0부터 시작해도 상관 없는데

arr에 저장할 땐 +1을 해줘서

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

1부터라는 조건을 만족시킨다!

 

 

 

ex) arr[k] = i;만 하면 출력이 0부터 됨

 

+아니면 그냥 반복문을 1부터 시작해도 됨! 취향 차이~

 

cout << '\n';

 

endl 쓰면 시간초과 나더라! 개행문자를 쓰자