[백준] 2011 암호코드 - DP JAVA

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

2011번: 암호코드

코드설명

DP 문제입니다.

 

문제에 주어진 예시와 함꼐 문제로직을 설명해보겠습니다.

input
25114

output
6

1. str = "25114" 로 저장합니다.

2. dp[]를 선언합니다. dp[N] 에서 N번째 자리수일때의 가능한 총 경우의 수를 의미합니다.

3. dp[0] = 1, 0번쨰 자리일때는 아무것도 없으므로 1가지 경우로 둡니다.

dp[1] = 1, 25114 에서 "2" 이므로 "B"로만 해석될 수 있습니다. 1가지 경우입니다.

dp[2] = 2,   "2 5 BE", "25 Y" 이렇게 BE이거나 Y 의 암호로 해석될 수 있습니다.

dp[3] = 3   "2 5 BE", "25 Y ", "25 1 YA"  이렇게 BE, Y, YA 의 암호로 해석될 수 잇습니다.

 

 

4. 위의 로직을 구현해보면,

dp[1] 일때, 즉 1자리수의 경우의 수를 구할때.  "2"(B) 한가지만 가능합니다.

dp[2] 일때, 즉 2자리수의 경우의 수를 구할때 먼저 "5"(E) 가 1부터 9까지인지 검사합니다. 이 조건을 통과한다면, DP[1]을 Dp[2] 에 더해줍니다. DP[2] += DP[1] . 여기서 DP[1]을 더해주는 이유는, DP[1]에서 "B"의 경우의 수가 가능했었는데 이것에 "B" 인경우와 "E"인 경우가 합쳐저 "BE"로 해석될 수 있으니 1가지를 더하는것입니다.

이제 "25" 를 가져옵니다. 25는 10부터 26까지의 값이기에 DP[1]의 값은 필요없습니다. 즉, "Y" 로 변합니다. 그러므로 DP[0]의 값을 더해주면 1이 더해지면서 2가 됩니다.

dp[3] 일때는 또한 마찬가지입니다. 1이 1부터 10사이인 경우에 "2 5 1" ( BEA ), 51 은 10부터 26 사이가 아니므로 "25 1" (YA) 로 dp[3] = 2 입니다.

...

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	String str = st.nextToken();
    	long[] dp = new long[str.length() + 1];
    	dp[0] = 1;
    	for(int i=1; i<=str.length();i++) {
    		int value = str.charAt(i-1) - '0';
    		if( value >=1 && value <= 9) { //한자리수를 검사할때는 1 부터 9까지만 가능합니다.
    			dp[i] += dp[i-1]; //
    			dp[i] %= 1000000;
    		}
    		if( i == 1 ) continue; //첫번쨰 글자일경우 중단한다.
    		
    		value = ( str.charAt(i-2) - '0' ) * 10 + str.charAt(i - 1) - '0';
    		if( 10 <= value && value <= 26) {
    			dp[i] += dp[i-2];
    			dp[i] %= 1000000; 
    		}
    	}
    	System.out.println(dp[str.length()]);
	}
}