[백준 / BOJ] - 15651번 N과 M(3) C++ 풀이

---

 

백준 - 단계별로 풀어보기 [15651] 

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

문제

 

 

 

풀이

 

순열을 구했던 15649번 문제에서 dfs에서 for문안에 if(!visited[i])를 넣어뒀던것만 제거하면 15651번 문제의 조건을 만족하는 출력값을 얻을 수 있다.

 

 

코드

 

#include <iostream>
#define MAX 9
using namespace std;

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = 1; i <= n; i++)
    {
            visited[i] = true;
            arr[cnt] = i;
            dfs(cnt+1);
            visited[i] = false;
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
}

 

 

평가

 

사실상 N과 M(1)에서 자기 자신을 다시 뽑을 수 있도록하는 규칙만 추가된 문제이다.

if(!visited[i])를 통해, 만약 1이라는 숫자가 뽑혀있다면 다음 원소로 1을 뽑지 않도록 했던 조건문을 제거해주면 15651번의 해답을 얻을 수 있다.