[백준, Java] 2011번, 암호 코드, (DP)

문제 링크

2011번: 암호코드

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 1 → A, 2 → B ... 26 → Z 으로 암호 코드를 변경할 수 있습니다.

2. 암호 코드에 대해서 해석되는 경우의 개수를 결과로 출력합니다.

3. 암호를 해석할 수 없으면 0을 결과로 출력합니다.

4. 값이 커질 수 있기 때문에 1000000을 나눈 나머지를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 암호 코드가 해석되는 경우의 개수를 점화식을 통해서 계산합니다.

 

3. 계산을 통해 얻은 경우의 개수를 결과로 출력합니다.

 

암호 코드 해석(DP)

 

암호 코드를 해석할 때에는 2가지 경우로 해석할 수 있습니다.

 

"23" 에서 2번째 암호 단어를 해석할 때

 

3 → C : 현재 암호 단어만 해석

 

23 → W : 앞 암호 값을 포함

 

으로 볼 수 있습니다.

 

DP[i] : i번째까지 암호를 해석했을 때 나올 수 있는 경우의 수

 

 

1. 현재 암호를 이용한 1 ~ 9까지의 알파벳으로 해석하기

 

해당 암호의 값이 0일 때에는 알파벳으로 해석하지 못합니다.

 

또한, 이전 해석된 암호의 경우에서 단순히 알파벳을 그대로 해석하는 것이기 때문에 다양한 경우의 수가 생기지 않습니다.

 

즉, 이전 암호 해석 경우의 수에서 더 늘어나지 않는다는 뜻입니다.

 

[점화식]

 

DP[i] = DP[i-1]

 

2. 바로 앞 암호를 이용해서 10 ~ 26까지의 알파벳으로 해석하기

 

26보다 큰 암호의 값은 알파벳으로 변경할 수 없습니다. 26 → Z까지이기 때문입니다.

 

해당 암호의 값은 앞의 암호 값까지 활용하지만 1개의 알파벳으로 변경되기 때문에 다양한 경우의 수가 생기지 않습니다.

 

즉, 2번 앞에 암호 해석 경우의 수에서 더 늘어나지 않는다는 뜻입니다.

 

[점화식]

 

DP[i] = DP[i-2]

 

 

암호를 알파벳으로 변경하는 2가지 경우를 살펴보았다면, 암호를 순차적으로 해석하면서 발견되는 경우를 파악하겠습니다.

 

1. 현재 암호가 0일 때

 

1) 앞에 암호가 1이거나 2일 때 (10, 20)

 

→ 알파벳으로 변경할 수 있습니다.

 

DP[i] = DP[i-2]

 

2) 앞에 암호가 0, 3 ~ 9일 때(00, 30, 40,  ... , 90)

 

→ 알파벳으로 변경할 수 없습니다.

 

암호를 해석할 수 없으므로 경우의 수는 0이 됩니다.

 

2. 현재 암호가 1 ~ 9일 때

 

1) 앞에 암호가 1이거나 2일 때(11 ~ 26)

 

→ 앞에 암호가 1일 때에는 1 ~ 9까지 왔을 때는 (앞에 암호와 같이 사용, 현재 암호만 사용) 2가지 경우를 만들 수 있습니다.

 

→ 앞에 암호가 2일 때에는 1 ~ 6까지 왔을 때만 (앞에 암호와 같이 사용, 현재 암호만 사용) 2가지 경우를 만들 수 있습니다.

 

DP[i] = DP[i-1] + DP[i-2]

 

2) 앞에 암호가 0, 3 ~ 9일 때(01, 02, .., 30, 31, .... 90, 91)

 

→ 앞에 암호를 사용하지 못하기 때문에 현재 암호만으로 알파벳으로 변경만 진행합니다.

 

DP[i] = DP[i-1]

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

암호 코드 : 25114

 

2. 암호 코드가 해석되는 경우의 개수를 점화식을 통해서 계산합니다.

 

25114

 

DP[i] : i번째까지 암호 코드 해석하는 경우의 수 정보

 

※ DP[0]이 1인 이유는 빈 암호 코드에 암호가 추가면 그 자체가 경우의 수가 되기 때문입니다.

 

	0	1	2	3	4	5
경우의 개수	1

 

1번째 암호 코드 해석( 25114 )

 

앞의 암호가 없기 때문에, 0으로 인지합니다.

 

현재 암호가 1 ~ 9이며, 앞에 암호가 0입니다.

 

점화식 : DP[1] = DP[1 - 1] (DP[i] = DP[i-1])

 

	0	1	2	3	4	5
경우의 개수	1	1

 

2번째 암호 코드 해석( 25114 )

 

앞의 암호 : 2

 

현재 암호가 1 ~ 9이며, 앞에 암호가 2입니다.

 

점화식 : DP[2] = DP[2 - 1] + DP[2 - 2] (DP[i] = DP[i-1] + DP[i-2])

 

	0	1	2	3	4	5
경우의 개수	1	1	2

 

3번째 암호 코드 해석( 25114 )

 

앞의 암호 : 5

 

현재 암호가 1 ~ 9이며, 앞에 암호가 5입니다.

 

점화식 : DP[3] = DP[3 - 1] (DP[i] = DP[i-1] )

 

	0	1	2	3	4	5
경우의 개수	1	1	2	2

4번째 암호 코드 해석( 25114 )

 

앞의 암호 : 1

 

현재 암호가 1 ~ 9이며, 앞에 암호가 1입니다.

 

점화식 : DP[4] = DP[4 - 1] + DP[4 - 2] (DP[i] = DP[i-1] + DP[i-2])

 

	0	1	2	3	4	5
경우의 개수	1	1	2	2	4

 

5번째 암호 코드 해석( 25114 )

 

앞의 암호 : 1

 

현재 암호가 1 ~ 9이며, 앞에 암호가 1입니다.

 

점화식 : DP[5] = DP[5 - 1] + DP[5 - 2] (DP[i] = DP[i-1] + DP[i-2])

 

	0	1	2	3	4	5
경우의 개수	1	1	2	2	4	6

 

 

3. 계산을 통해 얻은 경우의 개수를 결과로 출력합니다.

 

 

	0	1	2	3	4	5
경우의 개수	1	1	2	2	4	6

 

모든 암호 코드를 해석했을 때 경우의 수를 가리키는 값 : DP[5] = 6

 

6 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 점화식을 통해 각 암호 해석에 경우의 수를 DP[]에 저장합니다.
• 조건에 맞는 점화식을 통한 결과를 BufferdWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        //문자열 길이
        int len = str.length();
        //i번째까지 암호를 해석했을 때 나오는 경우의 수
        int[] DP = new int[len+1];
        int div = 1000000;
        //시작 값이 0이 아니면 항상 1인 값 초기화
        DP[1] = DP[0] = 1;
        //0으로 시작하면 암호를 해석할 수 없으므로 0으로 설정
        if(str.charAt(0) == '0'){
            DP[len] = 0;
        }else{
            //점화식을 통한 1 ~ n번째까지 암호 코드 해석 경우의 수 계산
            for(int i=2; i<=len;i++){
                //앞의 암호 값
                int preC = Character.getNumericValue(str.charAt(i-2));
                //현재 암호 값
                int curC =  Character.getNumericValue(str.charAt(i-1));
                //현재 암호가 0인 값일 때
                if(curC == 0){
                    //암호가 10, 20을 만들 때
                    if(preC == 1 || preC == 2){
                        DP[i] = DP[i-2];
                    }
                }else{	//현재 암호가 1 ~ 9일 때
                    // 11, 12, .., 91, 92일 
                    // 앞에 암호 포함 경우, 현재 암호만 경우 2가지 경우일 때
                    if(preC == 1 || (preC == 2 && curC <= 6)){
                        DP[i] = (DP[i-1] + DP[i-2]) % div;
                    }else{	//현재 암호로만 알파벳 해석 가능
                        DP[i] = DP[i-1];
                    }
                }
            }
        }
        //모든 암호코드를 해석했을 때 경우의 수 BufferedWriter 저장
        bw.write(String.valueOf(DP[len]));
        bw.flush();		//결과 출력
        bw.close();
        br.close();

    }
}