[BOJ] 2011 JAVA

문제

https://www.acmicpc.net/problem/2011

 

풀이

문제 이해하기

• 예제1) 25114

2까지만 보면 {B} = 1

25까지 보면 {BE('2', '5'), Y('25')} = 2

251까지 보면 {BEA('2', '5', '1'), YA('25', '1')} = 2

2511까지 보면 {BEAA('2', '5', '1'. '1'), BEK('2', '5', '11'), YAA('25', '1', '1'), YK('25', '11')} = 4

25114까지 보면 {BEAAD('2', '5', '1'. '1', '4'), YAAD('25', '1', '1', '4'), YAN('25', '1', '14'), YKD('25', '11', '4'), BEKD('2', '5', '11', '4'), BEAN('2', '5', '1', '14')} = 6

 

• 예제2) 1111111111 (1_111_111_111)

편의상 3자리로 끊어서 언더바를 추가함.

1까지 보면 {A} =1

11까지 보면 {AA('1', '1'), K('11')} =2

111까지 보면 {AAA(1, 1, 1), KA(11, 1), AK(1, 11)} =3

1_111까지 보면 {AAAA(1, 1, 1, 1), AAK(1, 1, 11), AKA(1, 11, 1), KAA(11, 1, 1), KK(11, 11)} =5

11_111까지 보면 {AAAAA(1, 1, 1, 1, 1), AAAK(1, 1, 1, 11), AAKA(1, 1, 11, 1), AKAA(1, 11, 1, 1), KAAA(11, 1, 1, 1), AKK(1, 11, 11), KAK(11, 1, 11), KKA(11, 11, 1)} =8

 

규칙이 조금 보이는 것 같지 않은가??

이전 자리수+현재자리수가 10~26 사이라면 dp[i]= dp[i-1]+dp[i-2]

else dp[i]=dp[i-1] 처럼 보인다.

 

맞는지 확인해보자

111_111 = 5+8 = 13

1_111_111 = 8+13 = 21

11_111_111 = 21+13 = 34 

111_111_111 = 34+21 = 55

1_111_111_111 = 55+34 = 89

 

예제 정답이 나왔다. 

 

코드

import java.util.Scanner;

public class Main {
    public static final int MAX_N = 5000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String code = sc.nextLine();
        code = " " + code;

        long [] dp = new long[MAX_N+1];

        // 초기값
        dp[0]=1;

        // 전개
        for (int i = 1; i < code.length(); i++) {
            int num = code.charAt(i) - '0';

            if(num>0){
                dp[i]=dp[i-1];
            }

            //i==1이면 i-2할 수 없음
            if(i==1 || code.charAt(i-1)=='0') continue;

            // 이전 자리+현재 자리
            num= (code.charAt(i-1) - '0')*10 + (code.charAt(i) - '0');
            // 1000000으로 나눈 나머지를 저장
            if(num>=10 && num<=26){
                dp[i]= (dp[i]+dp[i-2]) % 1_000_000;
            }

        }

        // output
        System.out.println(dp[code.length()-1]);
    }
}