백준 - 암호코드 (feat. Java)

문제 정보는 아래 링크를 확인해주세요!

[암호코드]

2011번: 암호코드

문제 접근 방법

• 암호코드의 첫째 자리부터 마지막 자리수까지 만들 수 있는 가지수를 구해나가는 DP 방식
• 만들 수 있는 문자의 번호는 1 ~ 26 이므로
• 현재값으로 1~9 사이의 문자를 만들 수 있는지 확인하고
• 현재값과 이전값으로 10 ~ 26 사이의 문자를 만들 수 있는지 확인한다.
• 유의해야할 부분은 각 DP 요소마다 범위를 넘어설 수 있으므로 1000000으로 나눠주고
• 암호코드의 첫 번째 요소가 '0'이면 문자를 만들 수 없는 상황이므로 코드의 첫 요소를 먼저 확인해준다.

[소스 코드]

 

package algorithm;

import java.util.Scanner;

public class Algorithm {

	public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String n = sc.nextLine();

        //코드의 첫 요소 확인
        if (n.charAt(0) == '0') {

            System.out.println(0);
            return;
        }

        //DP 배열 선언
        long[] dp = new long[n.length()+1];

        dp[0] = 1;
        dp[1] = 1;

        for (int i = 1,loop = n.length(); i < loop; i++) {

            char pre = n.charAt(i-1);
            char cur = n.charAt(i);

            //현재 요소로 1~9 사이의 문자를 만들 수 있는지
            if ('1' <= cur && cur <= '9') {

                dp[i+1] += dp[i];
                dp[i+1] %= 1000000;
            }

            //현재 요소와 이전 요소로 10~26 사이의 문자를 만들 수 있는지
            if (!(pre == '0' || pre > '2' || (pre == '2' && cur > '6'))) {

                dp[i+1] += dp[i-1];
                dp[i+1] %= 1000000;
            }

        }

        System.out.println(dp[n.length()]%1000000);
	}
}

 

[테스트]