[백준] 13908번 비밀번호

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q13908.java

비밀 번호를 알아내려고 한다. 3자리면 000~999 2자리면 00~99 까지 가능하다.
n자리의 비밀 번호중 m개의 숫자가 무조건 사용되어야한다. 예를들어 m이 2로 주어지고
3 4 가 주어지면 n이 2라면 34 43 밖에 비밀번호가 될 수 없다.
n과 m이 주어질 때, 비밀번호가 될 수 있는게 몇개인지 출력하여라.

처음 생각

n이 최대 7로 모든 경우를 보더라도 0000000~9999999로 천 만개만 봐주면된다. 따라서 완전 탐색을 통해 결과를 얻을 수 있다. 

다음 생각

천 만개에 대해서 매번 생성된 비밀번호마다 반복문을 이용해서 해당 숫자가 있나 없나를 보는것은 비효율 적이므로 재귀를 통해 조합을 생성해주면서 무조건 사용되어야하는 숫자를 사용했을 경우 카운트 변수 cnt를 +1 시켜주어 마지막에 이 cnt 변수가 m개 만큼 올라가 있으면 해당되는 비밀번호이므로 결과 변수를 +1 시켜주었다.

다다음 생각

해당 숫자를 한 번 사용하고 또 사용될 때 cnt 변수를 또 +1 시켜주면 안되기 때문에 한 번 사용하면 잠시 해당 값을 false로 바꿔주어 사용되더라도 cnt 변수가 올라가지 않게 하였다.

다다다음 생각

마우스가 갑자기 고장나 글이 조금 짧아졌지만 아래의 코드를 보면 위의 의미들이 전달 될 것 같다.

방안

package baekjoon.q10000;
 
import java.util.Scanner;
 
public class Q13908 {
    static int n,m;
    static boolean[] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        visited = new boolean[10];
        // 무조건 써야할 건 true 값을 넣어놔준다.
        for(int i=0;i<m;i++)
            visited[sc.nextInt()] = true;
        // 모든 경우를 살펴보자.
        solve(0,0);
        System.out.println(result);
    }
    
    static int result = 0;
    private static void solve(int idx,int cnt) {
        if(idx==n) {
            // 무조건 사용해야할 m개를 사용하지 않았으면 개수 카운트 x
            if(cnt!=m) return;
            result++;
            return;
        }
        
        for(int i=0;i<=9;i++) {
            // 무조건 사용해야할 것이라면
            if(visited[i]) {
                visited[i] = false;
                // 사용했다고 개수를 올려주자.
                solve(idx+1,cnt+1);
                visited[i] = true;
                continue;
            }
            solve(idx+1,cnt);
        }
    }
}