자바(백준) 2011 암호코드

오답 노트 & 새로 알게 된 점

해당 문제는 규칙성을 찾기 너무 어려웠다. 뭔가 알 것 같으면서도, 보이질 않았다.

26이라는 숫자가 중요한 것 같은데 어떻게 구현할지 생각이 1도 안 났다.

 

처음에 풀 때는, 반대로 풀었다.

즉, 예로 25114를 보면 4 -> 14 -> 114 -> 5114 -> 25114 이렇게 접근했다. dp를 배울 때, dp[N]이 원하는 답이라 하였는데, 위의 방법처럼 풀게 되면 반대로 풀게 되어 dp[1]인가 여기를 구해야했었다. 그래서 규칙성은 보이는데 어떻게 구현할지를 모르겠다고 말한 것이다.

 

구글링을 하여 힌트를 보니, 2 -> 25 -> 251 -> 2511 -> 25114로 접근하여 dp[N]이 원하는 답이 됐던 것이다.

 

규칙성은 숫자 하나를 비교하고, 그 다음에는 두 숫자를 비교하는 것이다. 두 숫자가 26보다 작거나 같으면 또 다른 경우가 생기게 된다.

dp[i]의 뜻은 i 자리일 때, 가능한 암호의 개수를 의미한다.

 

1. 숫자 하나를 비교할 때는 1 ~ 9 사이면 무조건 개수는 똑같다. 

26인지 아닌지는 다음에 비교할 거니까 일단은 dp[i] += dp[i-1]이다. 

 

2. 위에서 하게 되면 이제 두 숫자를 비교한다. 규칙성을 보면 두 숫자가 26보다 작거나 같으면 +dp[i-2]도 해줘야 한다.

 

두 번째 숫자 즉, 십의 자리 숫자가 0이면 반복문을 넘어가면 된다. 

 

251을 봐보자. 

 

1. 1은 1과 9 사이이므로 일단 25의 경우의 수를 더해준다. 

그러면 2+5와 25가 들어오는 것을 볼 수 있다.

 

2. 51을 비교해보자. 51은 26보다 크기 때문에 조건을 만족하지 못한다.

그래서 dp[i-1]과 경우의 수가 같다.

 

2511을 봐보자.

 

1. 1은 1과 9 사이이므로 일단 251의 경우의 수를 더해준다.

그러면 2+5+1, 25+1의 경우가 들어온다.

 

2. 11을 비교해보자. 11은 26보다 작거나 같기 때문에 조건을 만족한다.

그러면 앞의 25인 2+5, 25의 경우가 들어오게 된다.

그래서 dp[i-2]의 값도 더해준다.

 

---

 

코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MOD = 1000000;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
 
        int dp[] = new int[str.length() + 1];
        dp[0] = 1;
 
        for (int i = 1; i <= str.length(); i++) {
            int one = str.charAt(i-1) - '0';
            if (one >= 1 && one <= 9) {
                dp[i] += dp[i - 1];
                dp[i] %= MOD;
            }
 
            if(i == 1) continue;
 
            int two = str.charAt(i - 2) - '0';
 
            if(two == 0) continue;
 
            int ten = two * 10 + one;
 
            if (ten >= 10 && ten <= 26) {
                dp[i] += dp[i - 2];
                dp[i] %= MOD;
            }
        }
        System.out.println(dp[str.length()]);
    }
}