[코드트리] 특정 조건에 맞게 k개 중에 1개를 n번 뽑기 C++

문제

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition-under-constraint?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획 세우기

1이상 K이하의 숫자를 N번 골라 나올 수 있는 모든 서로 다른 순서쌍을 구하기(=1~K의 수로 이루어진 N자리 수 만들기)

단, 연속하여 같은 숫자가 3번 이상 나오는 경우는 제외

 

vector에 1~k 사이의 숫자를 넣다가(재귀 이용) 자릿수가 n이 되면 vector안에 있는 수를 출력 후 return

숫자를 넣을 때 이전의 숫자(curr_num-1)와 그 이전의 숫자(curr_num-2)가 지금 넣으려고 하는 수(i)와 같다면 연속하여 같은 숫자가 3번 이상 나오게 되므로 continue 하여 다른 수를 넣어준다.

 

풀이

#include <iostream>
#include <vector>

using namespace std;

int n, k;
vector<int> num;
//연속하여 같은 숫자가 3번 이상 나오는 경우는 제외
void MakeNum(int curr_num){
    // 종료조건
    if(curr_num==n){
        for(int i=0; i<n; ++i){
            cout << num[i] << " ";
        }
        cout <<'\n';
        return;
    }
    
    // 재귀 호출
    for(int i=1; i<=k; ++i){
        if(curr_num>1 && num[curr_num-1]==i && num[curr_num-2]==i) continue;
        num.push_back(i);
        MakeNum(curr_num+1);
        num.pop_back();
    }

}
int main() {
    cin >> k >> n;

    MakeNum(0);

    return 0;
}