(C++) - 백준(BOJ) 12101번 : 1, 2, 3 더하기 2

www.acmicpc.net/problem/12101

12101번: 1, 2, 3 더하기 2

backtracking문제였습니다.

 

풀이방법

 1. 1,2,3중에 중복가능하게 i개를 골라 식을 만들었을 때 num과 같다면 vector 변수 ans에 넣어줍니다.

 

 2. 매번 3개의 분기로 호출이 되므로 시간복잡도는 i * 3^i 가 됩니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,k;
vector <string> ans;
void backtracking(int idx,int m,int num,string op){
    if(idx == m){
        if (num == n) ans.push_back(op.substr(1,op.size()-1));
        return;
    }
    backtracking(idx + 1, m, num + 1, op + "+1");
    backtracking(idx + 1, m, num + 2, op + "+2");
    backtracking(idx + 1, m, num + 3, op + "+3");
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) backtracking(0,i,0,"");
    sort(ans.begin(),ans.end());
    if(ans.size() >= k) cout << ans[k-1];
    else cout << "-1";
}