[BaekJoon] 2780 비밀번호

1.  문제 링크

2.  문제

요약

• 위 그림처럼 비밀번호 패드가 있을 때, 석원이가 남겨둔 힌트를 이용하여 이 패드로 만든 힌트를 만족하는 비밀번호의 개수를 알아내는 문제입니다.
• 힌트
1. 비밀번호의 길이는 N입니다.
2. 비밀번호에서 인접한 수는 실제 비밀번호 패드에서도 인접해야 합니다.
• ex. 1의 경우 2와 4는 인접하고 5는 인접하지 않습니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수가 주어지고 두 번째 줄부터 테스트 케이스의 개수만큼 비밀번호의 길이 N이 주어집니다.
• 출력: 각 테스트 케이스에서 만족하는 비밀번호의 개수를 테스트 케이스 순서대로 출력합니다.

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과 인접한 숫자들을 뜻합니다.

1. 우선 각 숫자들의 인접한 숫자들을 HashMap에 저장해둡니다.
2. 행의 길이가 1000, 열의 길이가 10인 2차원 배열을 하나 만듭니다.(행의 길이가 1000인 이유는 문제에서 주어진 최대 비밀번호 길이가 1000이고 열의 길이가 10인 이유는 비밀번호 패드에 주어진 숫자가 10개이기 때문입니다.)
3. 비밀번호의 길이가 1인 경우에는 모든 숫자에 대해서 경우의 수가 1가지이기 때문에 길이가 1인 행은 모두 값을 1로 초기화합니다.
4. 비밀번호에서 다음 숫자에는 인접한 숫자만 올 수 있다는 성질을 이용하여 2차원 배열에 값들을 모두 채웁니다.
5. 힌트를 지킨 길이가 N인 비밀번호의 개수는 길이가 N일 때의 0부터 9까지의 비밀번호 개수를 모두 더하면 되므로 N번째 행의 모든 값을 더합니다.