코테 문제풀이 8일차

👑문제: [BOJ Gold5]

암호코드

풀이 시 고려해야 할 점

1. 해당 지점의 숫자를 바로 영단어로 바꿀 수 있는 경우 (1에서 9사이)
2. 해당 지점의 숫자는 못바꾸지만 두자리 수는 영단어로 바꿀 수 있는 경우(10,20)
3. 해당 지점의 숫자와 두자리 수 모두 못바꾸는 경우(ex 60)
4. 해당 지점과 두자리 수 모두 바꾸는 경우(ex 11)
   1번의 경우에는 dp[i] = dp[i-1]
   2번의 경우에는 dp[i] = dp[i-2]
   3번의 경우에는 암호 해석이 불가하므로 0을 출력,
   4번의 경우는 dp[i] = dp[i-1] + dp[i-2]

이렇게 총 4가지 경우를 모두 고려해야 한다. 또한 1000000으로 나눈 나머지를 출력해야 하는 조건도 매우 중요!

풀이 과정

package BOJ.DP;

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

public class G2011 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        String str = br.readLine();
        int[] dp = new int[str.length()+1];
        dp[0] = 1;
        if(str.charAt(0) >= '1' && str.charAt(0) <= '9') {
            dp[1] = 1;
            for (int i = 1; i < str.length(); i++) {
                char first = str.charAt(i);
                boolean f1 = false;
                boolean f2 = false;
                if(first >= '1' && first <='9') f1 = true;

                String sec = str.substring(i-1,i+1);
                if(Integer.parseInt(sec) >= 10 && Integer.parseInt(sec) <= 26) {
                    f2 = true;
                }

                if(f1 == false && f2 == true) {
                    dp[i+1] = (dp[i-1])%1000000;
                } else if (f1 == false && f2 == false) {
                    break;
                } else {
                    if(f2 == false) {
                        dp[i+1] = (dp[i])%1000000;
                    } else {
                        dp[i+1] = (dp[i]+dp[i-1])%1000000;
                    }
                }
            }
            System.out.println((dp[str.length()])%1000000);
        }
        else System.out.println(0);
    }
}

느낀점

4가지 경우를 모두 고려해야 하는 점이 살짝 까다로웠다.. 모든 경우의 수 생각하고 풀기!