12101번 1, 2, 3 더하기 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long int arr[1000001];

void print_nk(int n, int k) {
	if (n >= 4) {
		if (arr[n - 1] + arr[n - 2] < k) {
			cout << "3+";
			print_nk(n - 3, k - arr[n - 1] - arr[n - 2]);
		}
		else if (arr[n - 1] < k) {
			cout << "2+";
			print_nk(n - 2, k - arr[n - 1]);
		}
		else {
			cout << "1+";
			print_nk(n - 1, k);
		}
	}
	else {
		if (n == 1) {
			cout << "1";
		}
		else if (n == 2) {
			if (k == 1) {
				cout << "1+1";
			}
			else {
				cout << "2";
			}
		}
		else {
			if (k == 1) {
				cout << "1+1+1";
			}
			else if (k == 2) {
				cout << "1+2";
			}
			else if (k == 3) {
				cout << "2+1";
			}
			else {
				cout << "3";
			}
		}
	}
}

int main() {
	for (int i = 0; i < 1000001; i++) {
		arr[i] = 0;
	}
	
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;
	for (int i = 4; i < 1000001; i++) {
		arr[i] = (arr[i - 1] + arr[i - 2] + arr[i - 3]) % 1000000009;
	}

	int n, k;
	cin >> n >> k;
	if (arr[n] < k) {
		cout << "-1";
	}
	else {
		print_nk(n, k);

	}
	return 0;
}