[BaekJoon] 2780 비밀번호
1. 문제 링크
https://www.acmicpc.net/problem/27802. 문제
요약
- 위 그림처럼 비밀번호 패드가 있을 때, 석원이가 남겨둔 힌트를 이용하여 이 패드로 만든 힌트를 만족하는 비밀번호의 개수를 알아내는 문제입니다.
- 힌트
- 비밀번호의 길이는 N입니다.
- 비밀번호에서 인접한 수는 실제 비밀번호 패드에서도 인접해야 합니다.
- ex. 1의 경우 2와 4는 인접하고 5는 인접하지 않습니다.
3. 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class Main {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(){{
put(0, new ArrayList<Integer>(Arrays.asList(7)));
put(1, new ArrayList<Integer>(Arrays.asList(2,4)));
put(2, new ArrayList<Integer>(Arrays.asList(1,3,5)));
put(3, new ArrayList<Integer>(Arrays.asList(2,6)));
put(4, new ArrayList<Integer>(Arrays.asList(1,5,7)));
put(5, new ArrayList<Integer>(Arrays.asList(2,4,6,8)));
put(6, new ArrayList<Integer>(Arrays.asList(3,5,9)));
put(7, new ArrayList<Integer>(Arrays.asList(4,8,0)));
put(8, new ArrayList<Integer>(Arrays.asList(5,7,9)));
put(9, new ArrayList<Integer>(Arrays.asList(6,8)));
}};
int[][] dp = new int[1000][10];
public int[] getPWNum(int[] pw_size) {
int[] result = new int[pw_size.length];
for(int i = 0; i < dp[0].length; i++) {
dp[0][i] = 1;
}
for(int i = 1; i < dp.length; i++) {
for(int j = 0; j < dp[i].length; j++) {
for(int num : map.get(j)) {
dp[i][j] += dp[i - 1][num];
dp[i][j] %= 1234567;
}
}
}
for(int i = 0; i < pw_size.length; i++) {
for(int j = 0; j < dp[0].length; j++) {
result[i] += dp[pw_size[i] - 1][j];
}
result[i] %= 1234567;
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int num = Integer.parseInt(br.readLine());
int[] pw_size = new int[num];
for(int i = 0; i < num; i++) {
pw_size[i] = Integer.parseInt(br.readLine());
}
br.close();
Main m = new Main();
int[] result = m.getPWNum(pw_size);
for(int i = 0; i < result.length; i++) {
bw.write(result[i] + "\n");
}
bw.flush();
bw.close();
}
}
4. 접근
- 이 문제는 동적 계획법(Dynamic Programming)을 이용하여 풀 수 있는 문제입니다.
- 만약 비밀번호의 길이가 3이고 첫 번째 숫자가 4라면 그 다음에 올 수 있는 숫자는 현재 번호와 인접한 곳에 있는 번호들이기 때문에 1,5,9가 올 수 있을 것입니다.
- 이는 곧 길이가 3이고 첫 번째 숫자가 4인 비밀번호의 개수는 길이가 2이고 첫 번째 숫자가 1 또는 5 또는 9인 비밀번호의 개수를 뜻합니다.
- 이를 점화식으로 나타내면
- DP(N, num) = DP(N - 1, n1) + DP(N - 1, n2) + ...
- N은 비밀번호의 길이를 뜻하고 num은 N번째 자리수를 뜻합니다.
- n1, n2...는 num과 인접한 숫자들을 뜻합니다.
- 우선 각 숫자들의 인접한 숫자들을 HashMap에 저장해둡니다.
- 행의 길이가 1000, 열의 길이가 10인 2차원 배열을 하나 만듭니다.(행의 길이가 1000인 이유는 문제에서 주어진 최대 비밀번호 길이가 1000이고 열의 길이가 10인 이유는 비밀번호 패드에 주어진 숫자가 10개이기 때문입니다.)
- 비밀번호의 길이가 1인 경우에는 모든 숫자에 대해서 경우의 수가 1가지이기 때문에 길이가 1인 행은 모두 값을 1로 초기화합니다.
- 비밀번호에서 다음 숫자에는 인접한 숫자만 올 수 있다는 성질을 이용하여 2차원 배열에 값들을 모두 채웁니다.
- 힌트를 지킨 길이가 N인 비밀번호의 개수는 길이가 N일 때의 0부터 9까지의 비밀번호 개수를 모두 더하면 되므로 N번째 행의 모든 값을 더합니다.
Author And Source
이 문제에 관하여([BaekJoon] 2780 비밀번호), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@taeho97/BaekJoon-2780-비밀번호저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)