BOJ 16936, 나3곱2
ProblemSolving ·이 문제는 어떤 문제라고 말씀드려야 할 지는 모르겠지만 저는 재귀와 map을 사용해서 구현하였습니다.
풀이
처음에는 조건에 맞는 숫자를 배열에서 찾아 순열을 돌려야 되나 생각했지만 시간이 엄청나게 커질 것 같아서 어떻게 시간을 줄일까 생각했습니다.
그리고 찾은 방법이 다음에 올 숫자를 arr배열중에서 찾는 것이 아니라 조건에 맞는 숫자를 넣어보고 그 숫자가 사용가능한 숫자인지는 map을 사용해서 구분하였습니다. 배열로 구분하기에는 숫자의 범위가 long long형이기 때문에 map을 이용하였습니다.
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
typedef long long ll;
map <ll, int> m;
ll n,arr[101],ans[101],chk;
void go(ll now, int depth)
{
if (m[now] != 1)
return;
if (depth == n && chk == 0)
{
chk = 1;
for (int i = 1; i <= n; i++)
printf("%lld ", ans[i]);
printf("\n");
return;
}
if (ans[depth] % 3 == 0)
{
ans[depth + 1] = now / 3;
go(now / 3, depth + 1);
}
ans[depth + 1] = now * 2;
go(now * 2, depth + 1);
}
int main()
{
scanf("%lld", &n);
for (int i = 0; i < n; i++)
{
scanf("%lld", &arr[i]);
m[arr[i]] = 1;
}
for(int i=0;i<n;i++)
if (chk == 0)
{
ans[1] = arr[i];
go(arr[i], 1);
}
return 0;
}