[P388352] 비밀 코드 해독 (JAVA)

⭐️ 문제

비밀 코드 해독

---

🌟 풀이

• 알고리즘 : DFS + 조합
• 풀이과정 :

1. 1 ~ n 숫자 조합으로 만들 수 있는 5가지 숫자 arr 배열에 저장
2. check 함수에서 조합한 5가지 숫자가 입력한 정수와 시스템 응답에 맞는지 확인 

---

✨ 코드

public class P388352 {
    public static boolean[] visited;
    public static int arr[], answer;
    public static ArrayList<Integer> list;
    public int solution(int n, int[][] q, int[] ans) {
        answer = 0;

        arr = new int[5];
        visited = new boolean[n + 1];
        dfs(1, 0, n, q, ans);

        return answer;
    }

    public static void dfs(int start, int count, int n, int[][] q, int[] ans){
        if(count == 5){
            list = new ArrayList<>();
            for(int i = 0; i < 5; i++){
                list.add(arr[i]);
            }
            check(q, ans);
            return;
        }

        for(int i = start; i < n + 1; i++){
            if(visited[i]) continue;
            visited[i] = true;
            arr[count] = i;
            dfs(i, count + 1, n, q, ans);
            visited[i] = false;
        }
    }
    public static void check(int[][] q, int[] ans){
        int len = q.length;
        for(int i = 0; i < len; i++){
            int count = 0;
            for(int j = 0; j < 5; j++){
                if(list.contains(q[i][j])) count++;
            }
            if(count != ans[i]) return;
        }
        answer++;
    }
}

---

🤩

하필

조합만 구현할 줄 안다면 쉽게 풀 수 있는 문제~~~