[BaekJoon] 2011 암호코드

오태호·2022년 7월 15일
0

1.  문제 링크

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

2.  문제


요약

  • 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 하였습니다.
  • A를 1이라고 하고, B는 2, ..., Z는 26으로 암호화하기로 하였습니다.
  • 예를 들어, 500자리 글자를 암호화했다고 하면 나올 수 있는 해석이 많습니다.
  • 어떤 암호가 주어졌을 때, 암호의 해석이 몇 가지가 나올 수 있는지 구하는 문제입니다.
  • 입력: 첫 번째 줄에 5000자리 이하의 암호가 주어집니다. 암호는 숫자로 이루어져 있습니다.
  • 출력: 첫 번째 줄에 나올 수 있는 해석의 가짓수를 출력합니다. 가짓수가 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력하고, 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public long getInterpretNum(String code) {
		if(code.charAt(0) == '0') {
			return 0;
		}
		long[] dp = new long[code.length() + 1];
		dp[0] = 1;
		dp[1] = 1;
		for(int i = 2; i <= code.length(); i++) {
			char cur_char = code.charAt(i - 1);
			char prev_char = code.charAt(i - 2);
			if(cur_char == '0') {
				if(prev_char == '1' || prev_char == '2') {
					dp[i] = dp[i - 2] % 1000000;
				} else {
					break;
				}
			} else {
				if(prev_char == '0') {
					dp[i] = dp[i - 1] % 1000000;
				} else {
					int temp = (prev_char - '0') * 10 + (cur_char - '0');
					if(1 <= temp && temp <= 26) {
						dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000;
					} else {
						dp[i] = dp[i - 1] % 1000000;
					}
				}
			}
		}
		return dp[code.length()] % 1000000;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String code = br.readLine();
		br.close();
		Main m = new Main();
		bw.write(m.getInterpretNum(code) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

  • 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
  • 만약 주어진 암호의 첫 번째 자리가 0이라면 해당 암호는 해석할 수 없으므로 0을 출력합니다.
  • 각 숫자까지 만들 수 있는 암호의 경우의 수를 나타내는 1차원 배열 dp를 생성하고 첫 번째 숫자가 0이 아니라면 만들 수 있는 암호이므로 dp[1]의 값을 1로 초기화합니다.
  • 현재 확인하려는 수가 만약 0이라면, 앞에 오는 수가 1 또는 2가 아니라면 해석할 수 없기 때문에 해당 경우는 0을 출력합니다.
  • 앞에 오는 수가 1 또는 2인 경우는 앞에 오는 수와 0을 합하여 하나의 문자로 해석되기 때문에 dp[i - 2]의 값이 dp[i]의 값이 됩니다.
  • 현재 확인하려는 수의 앞에 오는 수가 0이라면 앞에 오는 수와 그 앞의 수가 하나의 문자로 해석되기 때문에 현재 확인하려는 수는 하나의 문자로 매핑되므로 경우의 수가 변함이 없어 dp[i - 1]의 값이 dp[i]의 값이 됩니다.
  • 위 경우 모두 아닌 경우는 앞 숫자와 연결했을 때의 숫자를 확인하여 해당 숫자가 하나의 문자로 해석될 수 있는 경우, dp[i]의 값은 dp[i - 1] + dp[i - 2]의 값이 되고
  • 앞 숫자와 연결했을 때의 숫자가 하나의 문자로 해석되지 못한다면 경우의 수가 변함이 없으므로 dp[i]의 값은 dp[i - 1]의 값이 됩니다.
profile
자바, 웹 개발을 열심히 공부하고 있습니다!

0개의 댓글