[Leetcode 9/100] Beautiful Arrangement - Medium

leetcode.com/problems/beautiful-arrangement/

Beautiful Arrangement - LeetCode

문제 풀이 방식

DFS를 활용하여 모든 경우의 수를 탐색하여 조건 처리

주의할 점

모든 경우의 수를 탐색하여 마지막에 조건을 처리하게 되면 TLE를 보게 된다.

그러므로 조건을 만족하지 않는 경우 재귀 함수를 호출하지 않도록 조건을 설정하는 것이 필수

소스코드

 

 class Solution {
        int res;
        boolean[] visitied;
        public int countArrangement(int n) {
            visitied = new boolean[n+1];
            DFS(n, 1, new int[n+1]);
            return res;
        }

        private void DFS(int n, int depth, int[] arr) {
            if(depth == n+1){
                res++;
                return;
            }

            for(int i=1; i<=n; i++){
                if(visitied[i]) continue;
                if(depth % i != 0 && i % depth != 0) continue;
                visitied[i] = true;
                arr[depth] = i;
                DFS(n, depth+1, arr);
                visitied[i] = false;
            }
        }

    }