백준 15651 N과 M (3)

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

아이디어

• 백트래킹 - 순열,조합
  • 중복 순열이기 때문에, 중복값 체크해줄 필요없음
  • 순열처럼 풀되 중복값 체크해주지 않으면 됨

시간복잡도 계산

• 10^M : 1e7 > 가능

자료구조

• 백트래킹 리스트 : vector
  • 최대값 7 > INT 가능

코드(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
int N,M;
vector<int> v;
 
void dfs() {
    if(v.size() == M) {
        for(int x : v) cout << x << ' ';
        cout << '\n';
        return;
    }
    
    for(int i=1; i<=N; i++) {
        v.push_back(i);
        dfs();
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> M;
    dfs();
    return 0;
}
 

문제유형

• 백트래킹 - 순열, 조합
  • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
  • 조합 : 리스트 마지막 다음부터 순회
  • 값 중복되지 않도록 : 재귀함수 내 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