🔗 링크

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

✏️ 문제

비밀번호 자릿수가 주어졌을 때 사용 가능한 모든 비밀번호 중 '비밀번호에 들어갈 수'가 모두 포함된 비밀번호의 개수를 구하는 문제입니다.

🧠 접근

기초적인 브루트포스 문제입니다.

모든 가짓수를 찾은 뒤 숫자 포함 판정

아래와 같이 구합니다.
정해진 자릿수가 되면 선견지명으로 알게 된 비밀번호의 자리가 포함되어 있는지 판정합니다.

private static void dfs(int depth, int target, int[] required, Integer[] result) {
        if (depth == target) {
            for (int i = 0; i < required.length; i++) 
                if (!Arrays.asList(result).contains(required[i]))
                    return;
            count += 1;
            return;
        }
        for (int i = 0; i < 10; i++) {
            result[depth] = i;
            dfs(depth + 1, target, required, result);
        }
    }

결과를 출력

조건을 만족할 때마다 dfs()에서 1씩 더해 주었습니다.
이 count를 출력하면 됩니다.

dfs(0, n, required, result);
System.out.print(count);

예외 처리 추가

m이 0일 경우 (선견지명으로 알게 된 비밀번호가 없는 경우) 두 번째 줄이 입력되지 않습니다.
입력되지 않을 경우 비밀번호는 10진수이고 모든 경우가 가능한 경우이므로 자릿수가 $n$일 때 경우의 수는 $10^n$가 됩니다.

if (m == 0) {
	System.out.print((int) Math.pow(10, n));
    System.exit(0);
}

📄 전체 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    private static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int[] nm = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = nm[0], m = nm[1];
        if (m == 0) {
            System.out.print((int) Math.pow(10, n));
            System.exit(0);
        }
        int[] required = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Integer[] result = new Integer[n];
        dfs(0, n, required, result);
        System.out.print(count);
    }

    private static void dfs(int depth, int target, int[] required, Integer[] result) {
        if (depth == target) {
            for (int i = 0; i < required.length; i++) 
                if (!Arrays.asList(result).contains(required[i]))
                    return;
            count += 1;
            return;
        }
        for (int i = 0; i < 10; i++) {
            result[depth] = i;
            dfs(depth + 1, target, required, result);
        }
    }
}