백준 15649 N과 M (1)

문제링크 : https://www.acmicpc.net/problem/15649

아이디어

• 백트래킹 - 순열
  • 이전값 중복체크만 해주면 됨

시간복잡도 계산

• 백트래킹 : 10^N : 1e8 > 가능

자료구조

• 백트래킹 vector

  • 최대 수 : 8이하 > INT 가능

코드(C++)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <iostream> #include <vector>   using namespace std;   vector<int> v; bool chk[10]; int N,M;   void dfs() {     // 개수 가득 차면 출력     if(v.size() == M) {         for(int x : v) cout << x << ' ';         cout << '\n';         return;     }          for(int i=1; i<=N; i++) {         if(chk[i]) continue;         chk[i] = 1;         v.push_back(i);                  dfs();                  chk[i] = 0;         v.pop_back();              } }   int main() {     fill(chk, chk+10, 0);     cin >> N >> M;     dfs();     return 0; }   Colored by Color Scripter

cs

문제유형

• 백트래킹 - 순열, 조합
  • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
  • 조합 : 리스트 마지막 다음부터 순회
  • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

• https://www.acmicpc.net/problem/15649
• https://www.acmicpc.net/problem/15650
• https://www.acmicpc.net/problem/15651
• https://www.acmicpc.net/problem/15652
• https://www.acmicpc.net/problem/15663