[코드트리 챌린지] 1주차 Backtracking - K개 중 하나를 N번 선택하기(Conditional) / 특정 조건에 맞게 k개 중에 1개를 n번 뽑기

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition-under-constraint/description

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

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> arr;

void Print() {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

void Choose(int cur_num) {

    if (cur_num == n + 1) {
        Print();
        return;
    }

    for (int i = 1; i <= k; i++) {
        if (cur_num >= 3 && arr[cur_num - 3] == i && arr[cur_num - 2] == i) {
            continue;
        }
        
        arr.push_back(i);
        Choose(cur_num + 1);
        arr.pop_back();
        
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> k >> n;

    Choose(1);
}

단순히 3자리 이상이 될 때 삽입하기 전 3개가 연속되는 지 확인하고 연속되면 continue 할 시 풀 수 있는 문제입니다.