백준 15652 N과 M (4)

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

아이디어

• 중복이 가능한 조합
• 기존 조합방법 : 리스트의 마지막값 다음부터 순회하며 백트래킹
• 중복이 가능하므로, 마지막값 부터 순회하면서 수행

시간복잡도 계산

• O(10^M) : 1e8 > 가능

자료구조

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

코드(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> v;
int N,M;
 
void dfs() {
    if(v.size() == M) {
        for(int x : v) cout << x << ' ';
        cout << '\n';
        return;
    }
    
    int last = 1;
    if(!v.empty()) last = v.back();
 
    for(int i=last; 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