BOJ-12101-1,2,3 더하기 2

필요한 지식

1. 완전탐색

접근

• n이 11까지 밖에 안되므로 재귀로 완전탐색한다.

• vector에 선택되는 한가지 숫자를 계속 넣어주면서 진행하다가 k번째가 된다면 재귀를 빠져나와 vector에 저장된 수를 거꾸로 꺼내준다.

코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, cnt = 0;
vector<int>v;
bool go(int sum) {
	if (sum == n) cnt += 1;
	if (cnt == k) return true;
	for (int i = 1; i < 4; i++) {
		if (sum + i <= n && go(sum + i)) {
			v.push_back(i);
			return true;
		}
	}
	return false;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	go(0);
	if (v.size()) {
		for (int it = v.size() - 1; it > 0; it--) cout << v[it] << "+";
		cout << v[0];
	}
	else cout << -1;
	return 0;
}