백준 2011번: 암호코드

 경우의 수를 구하는 문제이다.

 

25114를 예시를 보면

1. 2,5,1,1,4

2. 2,5,1,14

3. 2,5,11,4

4. 25,1,14

5. 25,11,4

6. 25,1,1,4

 위의 여섯 가지로 이루어져 있다. 

 

백준 9095 번 문제와 규칙이 비슷한 양상으로 이루어졌다.

 

dyii.tistory.com/7

백준 9095 번 : 1, 2, 3 더하기

그래서 예시를 한 글자씩 따져보았다.

 

2 (1개)

- 2

 

25  (2개)

- 2,5

- 25

 

251 (2개)

 - 2,5,1

 - 25,1

 

2511 (4개)

 - 2,5,1,1

 - 25,1,1

 - 2,5,11

 - 25,11

 

25114 (6개)

- 2,5,1,1,4

- 25,1,1,4

- 2,5,11,4

- 25,11,4

- 2,5,1,14

- 25,1,14

 

숫자로 풀어보면 위의 경우로 구할 수 있다.    *** 25114 에서 파란색은  2511 경우의 수고, 빨간색은 251 경우의 수다.

 

1. 일단, 가장 기본으로는 0이 아닌 숫자가 올 경우엔 앞 원소의 값을 그대로 가져올 수 있다.

 - 123이라는 숫자에 4가 추가된다면, 123을 구하는 경우에 원소 4만 추가하면 되기 때문에

123을 구한 경우의 수와 1234를 구하는 경우의 수는 같다.

arr [i] = arr [i-1]

 

2. 이번에 오는 숫자와 바로 앞의 숫자를 합했을 때 26보다 작은 수라면 경우의 수는 조금 달라진다.

 - 252란 숫자에 7을 추가한다면, 252를 구하는 경우의 수와 2527을 구하는 경우의 수는 같다.

 - 하지만, 252란 숫자에 1을 추가하게 된다면, 21이란 숫자의 경우를 생각해야 한다.

 -> 이 경우를 보면 25를 구한 경우의 수에 21을 추가하는 것이라고 볼 수 있다.

 즉,  25를 구하는 경우의 수와 252를 구하는 경우의 수의 합이 된다.

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

 

 

 

하지만, 여기에는 0이라는 변수가 존재한다.

 

26이란 숫자는  2,6과 26  경우가 있으나,

20이란 숫자에는 20 밖에 가지고 올 수밖에 없다.

 

그리고 00, 30,40 등... 은 무조건 오류이다.

 

결국, 뒷자리가 0일 경우에는 바로 앞자리의 숫자와 하나로 취급해야 한다.

즉, arr [i] = arr [i-2]가 된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	public static void main(String args[]) {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
    	  String[] sWord = br.readLine().split("");
    	
          int size = sWord.length;
          int[] word = new int[size];
          for(int i = 0;i<size;i++) {
        	  word[i] = Integer.parseInt(sWord[i]);
          }
          
    	  int[] arr = new int[size]; 
    	  if(word[0]==0) 
    		throw new Exception("0");
    	  
    	  arr[0] = 1;
    	  for(int i=1;i<size;i++) {
        	  int bNum = word[i-1];
        	  int aNum = word[i];
              // 10 < num < 27
        	 if( (bNum == 2 && aNum >0 && aNum<=6 ) ||(bNum==1 && aNum!=0)) {
        		arr[i]= i==1? 2:(arr[i-1]+arr[i-2])%1000000; 
        	 }  else if( (bNum>=3|| bNum==0) && aNum==0) {
                // 뒷자리가 0인 숫자 (10,20 제외)
        		  throw new Exception("0");
        	  } else if( bNum<=2 && aNum == 0) {
               // 10,20
        		  arr[i] = (i == 1)? 1:arr[i-2]%1000000; 
        	  } else { // 27 <= x (일의 자리 숫자가 0인 것 제외)
        		  arr[i]=arr[i-1]%1000000;
        	  }
          }
          System.out.print(arr[size-1]);
    	 
      }catch (Exception e) {
         System.out.println(0);
      }
	}
}

 

배열에 숫자를 넣으면서 어렵게 구했다. long으로 숫자를 받으면 조금 더 쉽게 구할 수 있다. 

 

그리고 아래의 코드는 다른 사람들의 코드를 참고한 것인데, 0을 따로 고려하는 경우를 추가해주지 않아도 된다.

 

 

		String words = sc.nextLine();
		int size = words.length();
		int arr[] = new int[size+1];
		int dp[] = new int[size+1];
		
		for(int i=0;i<size;i++) {
			arr[i+1]=words.charAt(i)-'0';
		}
		dp[0]=1;
		for(int i=1;i<=size;i++) {
			if(arr[i]!=0)
				dp[i]=(dp[i]+dp[i-1])%1000000;
			
			int num = arr[i]+arr[i-1]*10;
			if(num>=10 && num<=26) {
				dp[i]=(dp[i]+dp[i-2])%1000000;
			}
		}
		System.out.println(dp[size]);

0이 아닐 경우에는 경우의 수가 그 전의 원소와 같거나 크기 때문에, dp [i] = dp [i-1]을 해준다.

 

그리고 10 <=num <=26 일 때에는 dp [i-2]의 경우의 수를 더해준다.

뒷자리가 0일 경우에는 dp [i] 에는 0이 들어있기 때문에 dp[i] = dp[i-2] 가 되고,

0일 아닐 경우에는 dp[i] = dp [i-1] + dp [i-2]가 된다.