[백준] 16936 나3곱2

https://www.acmicpc.net/problem/16936

16936번: 나3곱2

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N;

vector <long long> v;
bool visit[110];
vector <long long> choice;

void dfs(int cnt, int target) {
	if(cnt == target) {
		for(int i=0; i<choice.size(); i++) 	
            printf("%lld ", choice[i]);
        exit(0);
	}
	for(int i=0; i<v.size(); i++) {
		if(visit[i] == true) continue;
		
		if(choice.size() >= 1) {
			long long before = choice[cnt-1];
			long long cur = v[i];

			if(before * 2 != v[i] && (before % 3 != 0 || before /3 != v[i])){
				continue;
			}
		}
		
		visit[i] = true;
		choice.push_back(v[i]);
		dfs(cnt+1, target);
		choice.pop_back();
		visit[i] = false;
		
	}
}

int main() {
	scanf("%d", &N);

	for(int i=0; i<N; i++) {
		long long tmp;
		scanf("%lld", &tmp);
		v.push_back(tmp);
	}
	
	dfs(0, N);

}

생각만 잘하면 쉬운 문제였는데

문제를 제대로 읽지 않아서 계속 틀림...

10^ 18까지의 수를 커버해야 하기 때문에, long long 형을 사용해주어야 하고, 

나눌때, 나머지도 고려해주어야한다.

 

시간초과 때문에, 모든 next_permutaion () 을 사용할 수 없다.

dfs 로 구하면서, 조건에 맞지 않을 경우, 더 이상 탐색하지 않도록 가지치기가 필요하다.

#include <iostream>
#include <vector>
#include <algorithm>
// 시간초과
using namespace std;
int N;


int main() {
	scanf("%d", &N);

	vector <long long> v;
	for(int i=0; i<N; i++) {
		long long tmp;
		scanf("%lld", &tmp);
		v.push_back(tmp);
	}

	do {
		bool success = true;

		for(int i=1; i<N; i++) {
			long long before = v[i-1];
			long long cur = v[i];		
			if(before * 2 != v[i] && (before % 3 != 0 || before /3 != v[i])){
				success = false;
				break;
			}

		}

		if(success) {
			for(auto b: v)
				printf("%lld ", b);
			exit(0);
		}


	}while(next_permutation(v.begin(), v.end()));
	
}