[BOJ] N과 M(2)

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

BOJ - N과 M(2)

문제 유형: 백트래킹, dfs, 재귀

문제 난이도: Silver III

시간 제한: 1초

메모리 제한: 512MB

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

배열을 (1, 2, ...,n-1 , n)로 만들어서, 이 배열에 대해 중복 없이 백트래킹 해주면 되다.

이 상태로 백트래킹하면서 순차적으로 순열들을 만들면, 순서는 보장되어있다.

solve(idx, seq, arr)을 실행하면, 

  만약 seq의 크기가 m이라면, 수열을 만들었다는 뜻이므로 출력한다.

  그게 아니고 idx가 n 이상이라면, 범위를 벗어났으므로 종료한다.

  둘다 아니라면, i =  idx ~ n-1까지 한 번씩 백트래킹을 호출한다.

    seq의 맨 뒤에 arr[i]를 추가했다가

    solve(i+1, seq, arr)을 호출하고 (같은 요소가 중복으로 들어갈 수 없으므로 i+1로 넘어간다)

    맨 뒤를 제거해준다.    

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, m;

void solve(int idx, vector<int> &seq, vector<int> &arr) {
  if (seq.size() == m) {
    for (int i = 0; i < m; ++i) {
      cout << seq[i] << " ";
    }
    cout << "\n";
    return;
  }
  if (idx >= n)
    return;

  for (int i = idx; i < n; ++i) {
    seq.emplace_back(arr[i]);
    solve(i + 1, seq, arr);
    seq.pop_back();
  }
}

int main(int argc, char *argv[]) {
  cin >> n >> m;
  vector<int> arr(n, 1);
  for (int i = 1; i < n; ++i) {
    arr[i] += arr[i - 1];
  }

  vector<int> seq;
  solve(0, seq, arr);

  return 0;
}

Silver oxide

 

산화 은(II)