[BOJ] 16936 - 나3곱2

문제 링크

이런걸 백트래킹이라고 하는걸까? 백트래킹은 제대로 배워본적이 없어서 이게 그게 맞는지 잘 모르겠다.
일단 내가 생각하기에는 그냥 완탐을 돌렸을 뿐이고.. 시간초과가 날 줄 알았는데 오버플로우 문제가 있었을 뿐 시간초과는 나지 않아서 의아했다.
(추가) 정확히 말하면 내가 푼 방식으로 풀면 int형으로 변수를 설정했을 때 오버플로우로 인해 정답을 찾을 수 없기 때문에 모든 경로를 다 보면서 시간초과가 난다. 아니 근데 생각해보면 오버플로우가 나면 어떤 방식으로도 틀리니까 내가 짠 방법때문에 틀렸다는 소리는 아닌데.. 아무튼.. 시간초과가 나지 않는 이유는 중간에 정답을 찾으면 그대로 빠져나와 프로그램을 종료하기 때문..인데 사실 테스트케이스를 어떻게 잘 짜면 이렇게 코딩해도 시간초과가 나게 할 수 있을 것 같은데… 그럴 의도는 아니었나보다.
여담이지만 solved.ac의 문제 난이도 설정 기준이 감이 안잡힌다. 난 왜 실버문제가 더 어려운지….
재귀를 쓰면 안되는데 습관이 들기도 하고 재귀 아니면 어떻게 코드를 짜야 할지 감이 안잡힌다.
이렇게 심심할때 문제를 풀면서 반복문으로 짜려고 의식적으로 노력을 해야겠다…

소스코드

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll arr[105], n;
bool visited[105];
vector<ll> v;

bool go(void) {
	if (v.size() == n) {
		for (ll i : v) {
			printf("%lld ", i);
		}
		return true;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i] && (v.back() == arr[i] * 3 || v.back() * 2 == arr[i])) {
			visited[i] = true;
			v.push_back(arr[i]);
			if (go()) {
				return true;
			}
			visited[i] = false;
			v.erase(--v.end());
		}
	}
	return false;
}

int main(void) {
	scanf("%lld", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld", arr + i);
	for (int i = 0; i < n; i++) {
		visited[i] = true;
		v.push_back(arr[i]);
		if (go()) break;
		v.clear();
		visited[i] = false;
	}
	return 0;
}