[백준]13908: 비밀번호 - JAVA

[백준]13908: 비밀번호

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

13908번: 비밀번호

풀이

이 문제의 입력 조건에서 n의 범위를 보면 1<=n<=7이다. n의 범위가 크지 않으므로 백트랙킹을 활용하여 완전탐색해 문제를 풀어 줄 것이다.

 

우선 항상 들어가야하는 숫자는 boolean타입의 배열에서 true로 설정하여 표시해준다. 그 다음에 백트랙킹을 하며 항상 들어가야 하는 숫자를 뽑았을 때에만 카운팅해주었다.

 

n개의 숫자를 뽑은 후, 카운팅 수가 m과 동일하다면 m개 만큼 카운팅이 되었는지(꼭 포함되어야 하는 m개의 수가 모두 포함되었는지) 확인한 후 m개 만큼 카운팅 되었다면 결과 개수를 더해주었다.

 

코드

import java.util.*;
 
public class Main {
 
    static int n, m;
    static int count;
    static boolean[] visited;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
 
        visited = new boolean[10];
        for(int i = 0; i < m; i++) {
            visited[scan.nextInt()] = true;
        }
 
        backtracking(0, 0);
        System.out.println(count);
    }
 
    public static void backtracking(int idx, int cnt) {
        if(idx == n) {
            if(cnt == m) count++; 
            return;
        }
 
        for(int i = 0; i <= 9; i++) {
            if(visited[i]) {
                visited[i] = false;
                backtracking(idx + 1, cnt + 1);
                visited[i] = true;
            } else {
                backtracking(idx + 1, cnt);
            }
        }
    }
}