[ 백준 ] 16936번 - 나3곱2 (C++)

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

16936번: 나3곱2

 

 

[ 문제풀이 ]

 

1. 수열을 입력받고, arr에 저장합니다.

 

2. 재귀함수를 이용하여 수열을 채워 나가는데, 이전 값에 2를 곱한 값이나 3을 나눈 값이 현재 수열의 값일 때만 수열에 넣어줍니다.

 

3. 모든 자리가 다 찬다면 그대로 출력해 줍니다.

 

[ 소스코드 ]

#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
ll arr[100];
ll ans[100];
int visited[100];
bool flag = false;
 
void dfs(int level)
{
    if (flag) return;
 
    if (level == N) {
        for (int i = 0; i < N; i++) {
            cout << ans[i] << ' ';
        }
 
        flag = true;
    }
 
    for (int i = 0; i < N; i++) {
        if (visited[i] == 0 && (ans[level-1] * 2 == arr[i] || (ans[level-1] % 3 == 0 && ans[level - 1] / 3 == arr[i]))) {
            visited[i] = 1;
            ans[level] = arr[i];
            dfs(level + 1);
            visited[i] = 0;
            ans[level] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < N; i++) {
        visited[i] = 1;
        ans[0] = arr[i];
        dfs(1);
        ans[0] = 0;
        visited[i] = 0;
    }
}