BOJ-16936 나3곱2

필요한 지식

1. 완전탐색

접근

• 입력받은 수열 B에 존재하는 원소들로 하나씩 시작해보면서 나3,곱2연산이 가능하다면(수열B에 원소가 존재한다면) 재귀적으로 연산을 수행한다.

코드(C++)

#include <iostream>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
set<ll>m;
vector<ll>v;
ll n, x;
void go(ll p, int depth) {
	if (depth == n) {
		for (auto it : v) cout << it << " ";
		return;
	}
	if (p % 3 == 0 && m.find(p / 3) != m.end()) {
		v.push_back(p / 3);
		go(p / 3, depth + 1);
		v.pop_back();
	}
	if (m.find(p * 2) != m.end()) {
		v.push_back(p * 2);
		go(p * 2, depth + 1);
		v.pop_back();
	}
	return;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll x; cin >> x; m.insert(x);
	}
	for (auto it : m) {
		v.push_back(it);
		go(it, 1);
		v.pop_back();
	}

	return 0;
}

결과