백준_2011 암호코드(자바) / DP

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_2011 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String tmp = br.readLine();
		int[] dp = new int[tmp.length() + 1];
		dp[0] = 1;
		dp[1] = 1;

		if (tmp.charAt(0) == '0') {
			System.out.println(0);
			return;
		}

		for (int i = 1; i < tmp.length(); i++) {
			char rear = tmp.charAt(i - 1);
			if (tmp.charAt(i) >= '1' && tmp.charAt(i) <= '9') {
				dp[i + 1] += dp[i];
				dp[i + 1] %= 1000000;
			}
			if (!(rear == '0' || rear > '2' || (rear == '2' && tmp.charAt(i) > '6'))) {
				dp[i + 1] += dp[i - 1];
				dp[i + 1] %= 1000000;
			}
		}
		System.out.println(dp[tmp.length()] % 1000000000);
	}
}

 

※ 내 생각
각 자릿수에 대한 DP를 이용해서 문제를 해결하는 문제입니다.
각 자릿수에서 만들수 있는 단어를 생각해볼 수 있습니다.
한자릿수에 대해서는 모두 가능하기 때문에 다 더해주면 됩니다.
여기서 중요한 포인트는 두자릿수를 만드는 경우를 처리하는 것입니다.