[백준] 2011번 문제 (암호코드) 파이썬(Python) 풀이

s = list(input().strip())
length = len(s)
dp = [0 for i in range(length + 1)]
dp[0], dp[1] = 1, 1

if s[0] == "0":
    print(0)
else:
    for i in range(2, length + 1):
        if int(s[i - 1]) > 0:
            dp[i] += dp[i - 1]
        num = int(s[i - 1]) + int(s[i - 2]) * 10
        if 10 <= num <= 26:
            dp[i] += dp[i - 2]
    print(dp[length] % 1000000)

한 20분 정도 규칙을 찾으려고 노력했으나, 솔루션이 떠오르지 않아 다른 사람의 풀이를 보았다.

풀이를 보니 생각보다 복잡하지는 않았다.

 

입력으로 주어진 숫자들을 하나부터 끝까지 훑어보며 dp에 경우의 수를 추가하며 푸는 방식인데,

 

만약 입력으로 주어진 숫자가 1234라면

우선 1을 검사한다.

 

숫자 1 하나만 놓고 보면 A로 밖에 해석이 되지 않아 

dp[1]에 1을 더해준다. (여기서는 초기에 초기화를 해줌)

 

그리고 숫자 12를 검사하는데,

숫자 12는 두 가지의 방법으로 해석이 될 수 있다.

 

1. A와 B 따로 하나 씩 보는 경우
2. 12를 L로 보는 경우

그렇다면 1번의 경우 B만 놓고 본다면 그 전번의 경우의 수와 같으니까, 

dp[i] += dp[i - 1]을 해준다.

 

그리고 이게 핵심인데

2번의 경우에는 숫자 12를 합쳐서 하나로 보게 되면 L이 나오게 된다.

그렇다면 경우의 수를 더 추가해줘야 되는데 그 코드가

dp[i] += dp[i - 2]가 된다.

 

처음에 왜 dp[i - 2]를 더하는지 몰랐는데

생각해보면 12를 하나로 놓고보면 L이 되고, 

그 상태엣 L은 바로 앞 단계가 dp[i - 2]이므로 dp[i] += dp[i - 2]를 통해 경우의 수를 추가해야 한다.

 

나머지 if문들은 예외처리라고 보면 된다.