방학공부 5일차

2011번을 끝으로 한동안은 DP외의 다른 문제들을 풀어볼 예정이다.
그래프, 탐색, 정렬등 다양한 알고리즘에 익숙해진 후에 분야별로 심화문제들을 풀어볼 예정이다.
처음에는 풀기 많이 힘들었던 문제들도 접근방향이나 속도면에서 많이 발전한 것 같아서 나름 만족스러운 1주일이였던 것 같다.

문제 : 백준 2011번
알고리즘 : DynamicProgramming

1 = A, 2 = B, ... ,26 = Z 와 같이 대치시켜 부호화를 진행할 때,
N자리의 숫자가 몇 개의 해석을 가질 수 있는 가 를 구하는 문제이다.

예를 들어,
11은 AA 혹은 K 로 해석될 수 있어서 2개,
27은 BG로만 해석될 수 있어서 1개의 경우의 수를 가진다.

정리하자면, 어떤 숫자는 두 가지의 방법으로 해석될 수 있다.
case1 : N번째 자리가 단독으로 사용되는 경우
case2 : N - 1번째 자리와 N번째 자리가 합쳐져서 사용되는 경우

여기서 case2의 조건은 10 <= (N-1번째 자리) X 10 + N번째 자리 <= 26

따라서
DP[N] : N자리 수가 해석될 수 있는 경우의 수 라고 할 때,
DP[N] = case1 + case 2 일 것이다.

이번엔 입력된 숫자안에 0이 있는 경우의 문제점을 살펴보자.

1. 첫번째 자리가 0일 때 해석불가
2. 중간에 0이 연속되는 경우 or 중간에 0을 해석할 수 없을 경우 해석불가

위 내용들을 참고하여 늘 하던대로 DP를 구현해보자.

import sys
input = sys.stdin.readline

Arr = list(map(int,input().strip()))
N = len(Arr)

DP = [0] * N

#첫자리
if Arr[0] > 0 : 
    DP[0] += 1
#두번째 자리
if N == 1:
    print(DP[0] % 1000000)
else :
    if Arr[1] > 0 :
        DP[1] = 1
    if 10 <= Arr[0] * 10 + Arr[1] <= 26 : 
        DP[1] += 1
    if Arr[0] * 10 + Arr[1] <= 9 :
        DP[N-1] = 0
    else :
        for i in range(2,N):
            if Arr[i] > 0 :
                DP[i] = DP[i - 1]
                
            if 10 <= Arr[i - 1] * 10 + Arr[i] <= 26 :
                DP[i] += DP[i - 2]
    print(DP[N-1] % 1000000)

위에서 말해던 중간에 0을 해석할 수 없는 경우에 대한 예외처리는 별도로 하지 않아도 된다. 어떤 이유로 DP[i-1]과 DP[i-2]가 0으로 결정되고 나면 DP[i]부터 DP[N]까지 자연스럽게 0으로 결정되기 때문이다.
이해가 잘 가지 않는다면 코드를 천천히 다시 읽어보면 도움이 될 것 같다.

종합 평가

시간복잡도 : O(N)
소요시간 : 45~60분
실패 횟수 : 1, 인덱스 범위 오류