[백준 2011][파이썬] 암호 코드 (타일링 문제와 동일)

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

2011번: 암호코드

 

알고리즘을 떠올리기 어려웠던 문제.

 

정말 많은 고민을 했었는데 문제를 푸는 알고리즘은 사실상 타일 문제와 동일했다.

 

https://blog.naver.com/growth_s/222759346988

[백준 11726, 11727][C++] 2xn 타일링

 

타일을 채우는 문제에 비해 이 암호 코드 문제는 조건이 조금 까다롭다는 점을 제외하면 알고리즘은 동일하다.

 

25114 라는 숫자가 있으면 dp[i]의 값은 인덱스 1부터 i까지의 가능한 경우의 수이다.

 

dp[1] = (2)의 가능한 암호 코드 수

 

dp[2] = (25)의 가능한 암호 코드 수

 

dp[3] = (251)의 가능한 암호 코드 수

.

.

.

 

여기서 조건을 고려해야 한다.

 

1. 인덱스 i에 해당하는 수에 인덱스 i-1가 붙어서 사용 가능할 때

 

에를 들어서 인덱스 i에 해당하는 수가 5이고 i-1에 해당하는 수가 2라면 둘을 붙여서 25로 사용할 수 있다.

 

이러한 경우는 dp[i]의 값은 dp[i-1] + dp[i-2]가 된다.

 

ex) 1112

 

dp[1]의 경우의 수 : (1) 

 

dp[2]의 경우의 수 : (1, 1), (11)

 

dp[3]의 경우의 수 : (1, 1, 1), (11, 1), (1, 11) 

 

한 번 색깔로 구분을 해보았다.

 

붙여서 사용이 가능할 때는 dp[i-1]에 붙이지 않은 값을 넣어주고 dp[i-2] 붙여서 넣어준다.

 

2. 인덱스 i에 해당하는 수에 인덱스 i-1가 붙어서 사용할 수 없을 때

붙일 수 없다는 뜻은 붙였을 때의 값이 10~26의 범위 밖이라는 것이다.

 

붙여서 사용할 수 없다면 dp[i-2]에 붙인 값을 넣을 수 없으므로 dp[i]는 dp[i-1]이 된다.

 

 

3. 인덱스 i에 해당하는 수에 인덱스 i-1가 붙을 수밖에 없을 때

인덱스 i에 해당하는 값이 0이고 인덱스 i-1에 해당하는 값이 1또는 2라면 이는 반드시 붙어서 10 또는 20을 만들어야 한다.

 

 이럴 때는 dp[i]는 dp[i-2]가 된다.

 

4. 인덱스 i에 해당하는 수를 어디에도 사용할 수 없을 때

 

인덱스 i에 해당하는 값이 0이고 인덱스 i-1에 해당하는 값이 1또는 2가 아니라면 이 값은 아예 사용할 수 없고 0을 출력하고 프로그램을 종료시킨다.

 

최종 코드

li=list(map(int,input()))
if li[0]==0:
    print(0)
    exit()
size=len(li)
dp=[0]*(size+1)

dp[0]=1
dp[1]=1
for i in range(1, size):
    if li[i-1]==1:
        if li[i]==0:
            dp[i+1]=dp[i-1]
        else:
            dp[i+1]=dp[i-1]+dp[i]
    elif li[i-1]==2:
        if li[i]==0:
            dp[i+1]=dp[i-1]
        elif 1<=li[i]<=6:
            dp[i+1]=dp[i-1]+dp[i]
        else:
            dp[i+1]=dp[i]
    else:
        if li[i]==0:
            print(0)
            exit()
        dp[i+1]=dp[i]
print(dp[size]%1000000)