📖 문제 링크
https://www.acmicpc.net/problem/2011
2011번: 암호코드
나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.
www.acmicpc.net
👩💻 문제풀이
DP문제 로드맵의 거의 마지막 문제인데 도저히 규칙도 안 찾아져서...^^
이러한 유형의 문제를 익힌다는 생각으로 아래의 블로그를 따라 작성하였다.
https://archive-me-0329.tistory.com/23?category=965963
백준 2011 파이썬
https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는
archive-me-0329.tistory.com
2011번 설명 중 가장 자세하고 이해가 쉬웠다. 혹 어려움을 겪고 계신다면 참고하시길!
✅ 최종 코드
n = list(map(int, input()))
l = len(n)
if n[0] == 0:
print(0)
exit()
else:
n = [0] + n
dp = [0] * (l+1)
dp[0] = 1
dp[1] = 1
for i in range(2, l+1):
if n[i] > 0:
dp[i] += dp[i-1]
if (n[i-1]*10 + n[i]) >= 10 and (n[i-1]*10 + n[i]) <= 26:
dp[i] += dp[i-2]
print(dp[l] % 1000000)
(정답률이 대략 19%밖에 안되는걸보니 나만 어려운 건 아니라는 위안을 삼아 본다.^^)
'알고리즘 > Python' 카테고리의 다른 글
| [백준/Python] 11650번: 좌표 정렬하기 (0) | 2022.01.23 |
|---|---|
| [백준/Python] 2751번: 수 정렬하기 2 (0) | 2022.01.23 |
| [백준/Python] 9461 파도반 수열 (0) | 2022.01.22 |
| [백준/Python] 2133 타일 채우기 (0) | 2022.01.22 |
| [백준/Python] 1699 제곱수의 합 (0) | 2022.01.18 |