https://www.acmicpc.net/problem/2011
시간 2초, 메모리 128MB
input :
- 암호(1 <= 암호 <= 5,000)
output :
- 나올 수 있는 해석의 가짓수 (1,000,000으로 나눈 나머지를 출력)
- 해석할 수 없는 경우에는 0을 출력.
조건 :
- A를 1이라고 하고, B는 2로, 그리고 Z는 26
ASCII 'A' = 65
호기롭게 알고리즘을 짰으나..
0 예외 처리 안 하고..
두 자리 연결 되는 경우에 10 ~ 26 사이여야 하는 예외 처리를 안 하고.
한 자리 일 때는 0 보다 커야 한다는 예외 처리 안 하고....
한 거는 i 번째 자리로 올 때 dp 어디서 계산 해야 하는가 밖에 없네;;;
항ㄹ니ㅏㅜ이ㅏㅜㄴ라ㅜㅇ린매ㅜㅑ
멘탈은 깨지는데
푸니까 기부니는 좋네.
처음에 생각해낸 알고리즘으로 길이가 1개일 때와 2개일 때를 나눈다.
길이가 1일 때 변환이 가능하면 DP에 1 , 불가능 하면 0
길이가 2일 때 변환이 가능 하면 DP에 1, 불가능 하면 0
행이 0 인 것을 계산 할 때는
if dp[0][i]:
dp[0][i] = dp[0][i - 2] + dp[1][i - 2]행이 1인 것을 계산 할 때는
if dp[1][i]:
dp[1][i] = dp[0][i - 1] + dp[1][i - 1]
dp[1][0] = 0
for i in range(1, len(data)):
if not (10 <= int(data[i - 1] + data[i]) <= 26):
dp[0][i] = 0
if not (1 <= int(data[i]) <= 10):
dp[1][i] = 0예외처리가 제일 중요.....
마지막에 나머지 안 구해서 되게 틀림...
힘들다 한 문제;;
import sys
data = list(sys.stdin.readline().strip())
dp = [[1] * len(data) for i in range(2)]
if data[0] == '0':
print(0)
else:
dp[1][0] = 0
for i in range(1, len(data)):
if not (10 <= int(data[i - 1] + data[i]) <= 26):
dp[0][i] = 0
if not (1 <= int(data[i]) <= 10):
dp[1][i] = 0
for i in range(2, len(data)):
if dp[0][i]:
dp[0][i] = dp[0][i - 2] + dp[1][i - 2]
if dp[1][i]:
dp[1][i] = dp[0][i - 1] + dp[1][i - 1]
print((dp[0][len(data) - 1] + dp[1][len(data) - 1]) % 1000000)
