[백준][DP] 2011. 암호코드 풀이

2011. 암호코드 풀이

2011번: 암호코드

• 문제 해석
  • 범위는 알파벳 26
  • 0은 해독 불가 -> 10, 20
  • 암호를 해석할 수 없는 경우에는 0을 출력한
• 작은 문제에서부터 큰 문제로 접근해가는 상향식 접근법
  • n = 25114 같은 숫자가 주어진다면 1번 인덱스 '2' 부터 차례로 몇 개의 암호 가짓수를 가지는지 계산하면 된다.

 

• 다른 사람 풀이

1) 현재 자리숫자가 0 보다 클 때 -> 이전 dp 값을 더한다

• 예) 2 5 1 1 4 에서 빨강색까지는 이미 구했다고 하자.
• 2  5  1  1 / 25  1  1 / 2  5  11 / 25  11 이렇게 4가지의 방법 뒤에 4를 독립적으로(한자리수로 생각) 붙힐 수 있으므로 4가지를 더할 수 있다.

2) 이전 자리수와 현재 자리수를 두 자리숫자로 볼 때 10~26사이의 숫자에 해당할 때 -> 전 전 dp 값을 더한다. 

• 2 5 1 1 4 에서 빨강색까지의 방법
  • -> 2  5  1 / 25  1 에다가 독립적으로 14를 붙힐 수 있으므로 2 가지를 더할 수 있다.

3) 처음 숫자가 0으로 시작하는 것은 10, 20으로도 만들 수 없으므로 아예 0으로 출력해주는 예외를 추가해주면 된다.

 

 

code = list(map(int, input().rstrip()))
n = len(code)
dp = [0 for _ in range(n+1)]
if code[0] == 0:
    print(0)
else:
    # 2번째자리에서 전전dp값을 더하기 위해 0 생성
    code = [0]+code
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        if code[i] > 0:
            dp[i] += dp[i-1]

        tmp = code[i-1]*10 + code[i]
        if tmp >= 10 and tmp <= 26:
            dp[i] += dp[i-2]

    print(dp[-1] % 1000000)