[Java] 백준 13908 - 비밀번호

[Java] 백준 13908 - 비밀번호

문제번호: 13908(비밀번호)

풀이(java)

백트래킹을 사용해서 풀이를 하면 간단하게 풀 수 있다. 전략은 모든 경우의 수 안에, 내가 알고있는 비밀번호들이 모두 담겨있으면 가능한 비밀번호라고 할 수 있다.

가장 먼저 입력으로 들어온 알고있는 번호를 know배열에 담아준다. 그 후에 백트래킹을 사용해 각 자리는 0 ~ 9 까지이며, n개를 골랐을 때 해당 비밀번호안에 know배열에 담겨있는 숫자들이 모두 속해있는지 판단을 해준다.

import java.io.*; import java.util.*; public class boj_13908 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int[] know; static Stack stack = new Stack<>(); static int result = 0; public static void main(String[] args) throws IOException { st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); if (m != 0) { know = new int[m]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < m; i++) { know[i] = Integer.parseInt(st.nextToken()); } } dfs(0, n, m); System.out.println(result); } public static void dfs(int start, int end, int m) { if (start == end) { for (int i = 0; i < m; i++) { if (!stack.contains(know[i])) return; } result++; return; } for (int i = 0; i <= 9; i++) { stack.add(i); dfs(start + 1, end, m); stack.pop(); } } }

from http://lee-s-k.tistory.com/13 by ccl(A) rewrite - 2021-12-30 05:27:33