[백준(baekjoon) 2011] 암호코드

문제

백준 2011

5000자리 이하의 입력 값(숫자)이 주어질 때,
아래와 같은 규칙으로 암호화 할 때, 가능한 문자의 경우의 수는

• A : 1, B : 2, … , Z : 26
• 예시 : 25114를 영어로 바꾸면
  
  • ”BEAAD” = {2, 5, 1, 1, 4}
  • “YAAD” = {25, 1, 1, 4}
  • “YAN” = {25, 1, 14}
  • “YKD” = {25, 11, 4}
  • “BEKD” = {2, 5, 11, 4}
  • “BEAN” = {2, 5, 1, 14}

해결

정답률이 낮아서 어려울지 알았지만, DP를 사용하면 생각보다 간단하게 풀린다.
그런데 엄청 틀렸다. 예외처리를 안했기 때문….
내 생각에 이 문제는 DP가 아니라 예외처리 문제이다….

예외처리

문제만 읽고 처음엔 0 input이 안 들어오는줄 알았지만… 들어온다…!
따라서, 0케이스 처리를 잘 해주면 된다.

• 예시 : input = 1027
  
  • {1, 2, 7}
  • {1, 2, 7}

90% 이상에서 틀리는 경우엔 input = 0인 경우일거에요!

알고리즘

DP bottom-up 방식으로 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

원리

문자열로 입력 받아 한 자리의 문자씩 접근해 풀면된다.

1. 자연수인 경우
   
   • input[now] > '0'
   • 1의 자리 숫자를 알파벳으로 변경할 수 있다. (A ~ I)
   • 경우의 수 = dp[i - 1]
2. 두자리 수(1의 자리 = 자신)가, 10이상 26이하 일 경우
   
   • 두자리 수 = (input[now - 1] - '0') * 10 + (input[now] - '0')
   • 10의 자리를 체크하는 것이므로 10이상
   • 알파벳을 나타낼 수 있는 26이하
   • 경우의 수 =dp[i - 2]

최종 값 = 1번 결과 + 2번 결과

유의사항

1. 쉬운 계산을 위하여 dp의 크기를 input의 크기보다 1크게 만들어 dp[0] = dp[1] = 1로 초기화를 시켜준다.
   
   • 위의 그림 5의 경우를 보면 이해가 쉽다.
2. 유의 사항 1번으로 인해 input = 0 일 경우 정답이 1이 나온다.
   하지만 정답은 0이므로 예외처리가 필요하다.

구현 java

Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        String input = sc.nextLine();
7.        int mod = 1000000;
8.        int[] dp = new int[input.length() + 1];
9.        dp[0] = dp[1] = 1;
10.        for (int i = 2; i <= input.length(); i++) {
11.            int now = i - 1;
12.            if (input.charAt(now) > '0')
13.                dp[i] = dp[i - 1];
14.            int su = (input.charAt(now - 1) - '0') * 10 + (input.charAt(now) - '0');
15.            if (su >= 10 && su <= 26)
16.                dp[i] = (dp[i] + dp[i - 2]) % mod;
17.        }
18.        System.out.println(input.equals("0") ? 0 : dp[input.length()]);
19.    }
20.}

결과