[백준] 2011번 암호코드 for JAVA

문제설명

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

 

제한사항

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

 

문제풀이

이번 문제는 최적화 문제로, 동적 계획법(DP)을 적용하여 푸는 문제입니다.

예시에 명시되어있는 25114을 Step별로 구분하여 경우의 수를 알아보겠습니다.

 

Step1

첫번째 자리 2입니다. 경우의 수는 1가지입니다.

 

Step2

두번째 자리는 5로, 두번째 자리까지 암호화가 가능한 경우는 아래와 같이 2가지입니다.

1. 2-5
2. 25

 

Step3

3번째 자리는 1로, 2번째 자리인 5와 결합하였을 때 숫자 51이 되므로 암호화가 불가능합니다. 따라서 암호화가 가능한 경우는 Step2와 동일한 2개가 됩니다.

1. 2-5-1
2. 25-1

즉, 'Step3의 경우의 수 = Step2 경우의 수'라는 것을 알 수 있습니다.

 

Step4

4번째 자리는 1로,  4번째 자리만 사용하는 1과 3번째 자리와 결합한 숫자인 11 을 모두 암호로 사용할 수 있음을 확인할 수 있습니다. 따라서 경우의 수는 총 4개가 됩니다.

• 암호화되는 수
  • 1인 경우 : Step3의 case에 각 각 '1'이라는 암호가 추가됨 (1-1, 2-1)
  • 11인 경우 : Step2의 case에 각 각 '11'이라는 암호가 추가됨 (1-2, 2-2)

1-1. 2-5-1-1
1-2. 2-5-11
2-1. 25-1-1
2-2. 25-11

즉, 'Step4의 경우의 수 = Step2 경우의 수 + Step3의 경우의 수'라는 것을 알 수 있습니다.

 

위 Step1~4를 통해 규칙을 알아낼 수 있습니다.

• 한 자리만 암호화가 가능한 경우에는, code[i] = code[i-1]
• 두 자리까지 암호화가 가능한 경우, code[i] = code[i-1] + code[i-2]

 

위 규칙에는 몇 가지 조건이 필요합니다. 

입력된 값이 해석이 가능해야하므로, 0이 포함된 경우에 대한 조건이 필요합니다.

• 복호화될 수 없는 0에 대한 조건
  • 0으로 시작
  • 100 이하면서  암호숫자인 10, 20을 제외한 10의 배수(30, 40, 50,..., 90)
  • 00을 포함

 

또한, 2자리수를 선택하였을 때 해당 숫자가 복호화가 가능한지 판단해야합니다.

• 2자리수의 복호화 가능 조건
  • 입력값은 0보다 크고 26보다 작거나 같음
  • 10, 20 이면 두자리수일때만 복호화가 가능

 

위 규칙과 조건을 적용한 솔루션입니다.

dp함수에서 조건에 따라 경우의 수를 계산하도록 구현하였으며, 재귀함수를 활용했습니다.

 

Solution

import java.util.Scanner;

public class Main {
	static String input;	// 입력값
	static StringBuilder sb = new StringBuilder();
	static int code[], length;	// 입력값의 자릿수별 경우의 수가 들어갈 배열

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		input = sc.nextLine();
		code = new int[input.length() + 1];
		length = code.length + 1;
		int res = 0;	// 결과값
		code[0] = 1;	// 배열의 0, 1번째 값을 1로 초기화 
		code[1] = 1;
		if (length > 1 && input.charAt(0) != '0') {
			dp(2);
			res = code[length - 2];
		}
		System.out.println(res);
	}

	private static void dp(int idx) {
		if (idx == length - 1)
			return;

		int two = Integer.parseInt(input.substring(idx - 2, idx));
		if (two == 0) {
			return;
		}
		if (two <= 26 && two > 10 && two != 20) {
			code[idx] = (code[idx - 1] + code[idx - 2]) % 1000000;
		} else if (two == 10 || two == 20) {
			code[idx] = code[idx - 2] % 1000000;
		} else if (two % 10 == 0) {
			return;
		} else {
			code[idx] = code[idx - 1] % 1000000;
		}
		dp(idx + 1);
	}
}

 

문제 바로가기

2011번: 암호코드