[백준-자바] N_2011 암호코드

0woy·2024년 2월 25일

DP 백준

코딩테스트

목록 보기

11/14

📜 문제

1~26(A-Z) 숫자를 사용하여 암호코드 만듦
어떤 암호가 주어졌을 때 복호화 가능한 경우의 수 구하기

DP 문제이다.
0이 나온 경우, 예외를 고려해서 문제를 풀어나가는 게 포인트라고 생각한다!

규칙 찾기

11205210 암호코드를 예시로 규칙을 찾아보겠다.

dp[n] :가짓수 저장, dp[0]=1, dp[1]=1_
i: 현재 인덱스
처음 인덱스는 1로 설정하여 시작한다. (1120.. 의 경우 1부터 시작)

암호코드를 두 자릿수로 끊어서 확인.
1-1. 끊은 숫자가 10~26 사이인 경우 dp[i-1]과 dp[i-2] 를 더한 값을 dp[i]에 저장
ex) 1 1 2 0... 에서 1,1 혹은 11의 경우가 나옴
그 외의 경우 dp[i]에 dp[i-1] 값을 저장.
현재 숫자가 0인 경우, 이전 숫자를 확인.
3-1) 이전 숫자가 1 또는 2가 아닌 경우, 잘못된 암호코드이므로 0 출력 후 프로그램 종료.
3-2) 이전 숫자가 1 또는 2인 경우, dp[i]에 dp[i-2] 값을 저장.
0은 단독으로 존재할 수 없어서 10 또는 20 같은 단일 암호로 사용되기 때문

계산 과정

인덱스	현재 숫자	dp
2	11	dp[2] = dp[1]+dp[0] = 2
3	12	dp[3] = dp[2]+dp[1] = 3
4	0	dp[4] = dp[2] = 2
5	5	dp[5] = dp[4] = 2
6	52	dp[6] = dp[5] = 2
7	21	dp[7] = dp[6]+dp[5] = 4
8	0	dp[8] = dp[6] = 2

👀 왜 위와 같이 dp[i] 값을 결정하는가?

11205210 를 예시로 보자.
1 - | 1 |
11 - | 1,1 | 11 |
112- | 1,12 | 1,1,2 | 11,2 |
1120 - | 1,1,20 | 11,20 |
11205 - | 1,1,20,5 | 11,20,5 |
112052 - | 1,1,20,5,2 | 11,20,5,2 |
1120521 - | 1,1,20,5,21 | 11,20,5,21 | 1,1,20,5,2,1 | 11,20,5,2,1 |
11205210 - | 1,1,20,5,2,10 | 11,20,5,2,10 |

112인 경우, 1에서 12을 추가한 경우, 11에서 2를 추가한 경우와 같으므로 dp[4]=dp[3]+dp[2]= 3

1120인 경우, 숫자 20만 허용되므로, 11인 경우에 20을 추가한 경우와같으므로
dp[5]=dp[3]= 2

11205인 경우, 1120의 경우에 5를, 112에 05를 추가한 경우지만, 05는 존재할 수 없으므로 1120에 5를 추가한 경우만 허용된다. dp[6]=dp[4]= 2

위 규칙대로 과정을 반복하면 dp[8] = 2가 된다.

✍ 부분 코드 설명

입력 및 예외 처리

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = br.readLine();
	int len = n.length();
	long[] dp = new long[len + 2];
	if(n.charAt(0)=='0'){
		System.out.println(0);
        return;
	}
        ...

변수 n에 암호코드를 입력받는다.
만일, 맨 앞자리가 0으로 시작한다면 잘못된 암호이므로 0을 출력하고 프로그램을 종료한다.

암호 코드 해독하기

	    else {
            dp[0] = 1;
            dp[1] = 1;
            for(int i=2;i<=len;i++){
                if(n.charAt(i-1)=='0') {
                    char prev = peek(i - 2);
                    if (next == '1' || next == '2') {
                        dp[i] = dp[i - 2] % 1000000;
                    } else {
                        System.out.println(0);
                        return;
                    }
                }
                else {
                    int next = Integer.parseInt(n.substring(i-2, i));
                    if (next > 9 && next < 27) {
                        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000;
                    } else {
                        dp[i] = dp[i - 1] % 1000000;
                    }
                }
            }
        }

현재 숫자가 0인 경우, 앞전 숫자를 확인한다.
1 또는 2라면 dp[i-2] 값을 저장하고 그렇지 않다면 잘못된 암호코드이므로 0을 출력한 후 프로그램을 종료한다.
현재 숫자가 0이 아닌 경우 두자리 수를 가져온다. 10~26 사이의 숫자인 경우 dp[i-1]+dp[i-2] 값을 저장하고, 그렇지 않은 경우 dp[i-1] 값을 저장한다.

🍳 전체 소스 코드


public class N_2011 {
    static String n;
    static public char peek(int idx){
        if(idx > n.length()-1) return '0';
        return n.charAt(idx);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = br.readLine();
        int len = n.length();
        long[] dp = new long[len + 2];
        if(n.charAt(0)=='0'){
            System.out.println(0);
            return;
        }
        else {
            dp[0] = 1;
            dp[1] = 1;
            for(int i=2;i<=len;i++){
                if(n.charAt(i-1)=='0') {
                    char next = peek(i - 2);
                    if (next == '1' || next == '2') {
                        dp[i] = dp[i - 2] % 1000000;
                    } else {
                        System.out.println(0);
                        return;
                    }
                }
                else {
                    int next = Integer.parseInt(n.substring(i-2, i));
                    if (next > 9 && next < 27) {
                        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000;
                    } else {
                        dp[i] = dp[i - 1] % 1000000;
                    }
                }
            }
        }
            System.out.println(dp[len]%1000000);
    }
}