백준: N과 M

문제

설명

  • 1부터 N까지의 카드 중에서 M개를 뽑는 경우의 수를 구하라!
  • 단, 순서가 있음을 주의
    • 즉, 1 44 1은 다른 것으로 취급

알고리즘

  • n_array, used_n 선언
    • 첫 번째 변수는 출력할 수를 담기 위한 벡터[길이 = M]
    • 두 번째 변수는 이 수를 방문 했는가?를 확인하기 위한 벡터[길이 = N]
  • dfs(depth) 시작[depth 초기값 = 0]
    • 만약 depth == M이라면
      • n_array에 있는 내용을 출력하고 리턴
    • 아니라면
      • i = 0; i < n; i++ 반복문 실행
        • 만약 탐방하지 않은 수가 있다면
          • 해당 수를 탐방했다고 표시하고 dfs(depth+1) 실행
          • 실행 후 탐방을 하지 '않았다고' 표시함[왜냐: 순서가 있기 때문!]

    코드

#include <vector>
#include <cstdio>

using namespace std;

vector<bool> used_n;
vector<int> n_array;

int n, depth;

void dfs(int cur_depth) {
    if (cur_depth == depth) {
        for (int tmp : n_array) {
            printf("%d ", tmp);
        }
        printf("\n");
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!used_n[i]) {
            used_n[i] = true;
            n_array[cur_depth] = i+1;
            dfs(cur_depth + 1);
            used_n[i] = false;
        }
    }
}

int main(void) {
    scanf("%d %d", &n, &depth);

    // Resize Used
    used_n.resize(n, false);

    // Init Vector
    n_array.resize(depth, 0);

    dfs(0);
    return 0;
}

좋은 웹페이지 즐겨찾기