16936 나3곱2

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

16936번: 나3곱2

나3곱2 스페셜 저지

 Gold V
난이도 제공: solved.ac

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

870

350

273

38.944%

문제

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

나3곱2 게임을 진행하면서, 만든 수를 모두 기록하면 수열 A를 만들 수 있다. 예를 들어, x = 9, N = 6이고, 적용한 연산이 곱2, 곱2, 나3, 곱2, 나3인 경우에 A = [9, 18, 36, 12, 24, 8] 이다.

수열 A의 순서를 섞은 수열 B가 주어졌을 때, 수열 A를 구해보자.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열 B가 주어진다. B에 포함된 원소는 1018 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 A를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

 

 

풀이)

 

1. 시간복잡도 수열의 길이 N * 연산횟수 N-1 * 수열내에 있는지 비교(N)  => O(N^3) = 100^3 =100만

 

2. 문제의 조건에 나3 은 3으로 나누어 떨어지는 경우만 가능하다.

 

3. 수열의 길이 N번동안 각 연산 (나3, 곱2)가 N-1번 진행하면서

 연산 결과 값이 수열의 길이내 존재하는지 비교하여 있으면 이어서 연속해서 구해본다.

 

4. 연속해서 구해보는건 재귀를 통해 구현.

 

#include<iostream>
#include<vector>

using namespace std;
void go(long long n, vector<long long> &ans_v);

int N;
vector<long long> v(N);
bool isend = false;
int main(void)
{
	cin >> N;
	
	for (int i = 0; i < N; ++i)
	{
		long long a=0;
		cin >> a;
		v.push_back(a);
	}
		
	for (int i = 0; i < N; ++i)
	{
		vector<long long> ans_v;
		ans_v.push_back(v[i]); //N-1번 연산
		go(v[i], ans_v);
	}
	return 0;
}
void go(long long n, vector<long long> &ans_v)
{
	if (isend) return;
	if (ans_v.size() == N) //나누기3 곱하기2가 N-1번 완료한 경우 출력
	{
		for (int i = 0; i < ans_v.size(); ++i)
		{
			cout << ans_v[i] << ' ';
		}
		cout << '\n';
		isend = true; //한번만 출력하고 끝냄.
		return;
	}
	
	long long tmp=0;
	bool isgo = false;
	if (n% 3 == 0) //3으로 나누어 떨어지는 경우
	{
		isgo = true;
		tmp = n / 3;
	}
	long long tmp_2 = n * 2;

	for (int i = 0; i < N; ++i)
	{
		if (tmp == v[i] && isgo) //나누기3  case1
		{
			ans_v.push_back(tmp);
			go(tmp, ans_v);
		}

		if (tmp_2 == v[i]) //곱하기2 case2
		{
			ans_v.push_back(tmp_2);
			go(tmp_2, ans_v);
		}
	}
}