[BOJ] 2011. 암호 코드

Jimeaning·2023년 4월 1일

코딩테스트

목록 보기

39/143

Python3,DP

문제

입출력

입출력 예시

주요 포인트

알파벳은 26개이므로 암호 코드는 1부터 26까지 가능하다.

만약 입력 받은 숫자가 0으로 시작한다면 만들 수 없으므로 0을 출력하고 종료한다.

한 자리일 때 경우의 수는 모두 1이다. (1~26사이에 있기 때문)
두 자리일 때는 10~26 사이에 있을 때만 경우의 수가 하나 더 증가한다.

이를 식으로 나타내면,
한 자리만 가능할 때의 경우의 수는 dp[i] += dp[i-1]
두 자리도 가능할 때의 경우의 수는 dp[i] += dp[i-2] 가 된다.

dp[0]에 1을 넣어 식을 맞춰 준다.

최종 코드

n = list(map(int, input()))

dp = [0 for i in range(len(n)+1)]

if n[0] == 0:
    print('0')
    exit(0)
    
dp[0] = dp[1] = 1
n = [0] + n

for i in range(2, len(n)):
    if n[i] > 0:
        dp[i] += dp[i-1]
    tmp = n[i-1] * 10 + n[i]
    if tmp >= 10 and tmp <= 26:
        dp[i] += dp[i-2]

print(dp[len(n)-1] % 1000000)