(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/2011
사용 알고리즘
- DP
풀이
- d[i] = i번째 문자까지 해석했을 때 나올 수 있는 해석의 가짓수
- i - 1과 i를 붙였을 때 10 ~ 26인 경우,
d[i] = d[i - 1] + d[i - 2]
- i - 1과 i를 붙였을 때 10 ~ 26이 아닌 경우,
d[i] = d[i - 1]
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/2011.cpp
#include <cstdio> #include <cstring>
int d[5003];
int main(void) { char pw[5003]; scanf("%s", pw + 1); int len = strlen(pw + 1); d[0] = 1; for (int i = 1; i <= len; ++i) { int x = pw[i] - '0'; if (1 <= x && x <= 9) d[i] += d[i - 1]; if (i == 1) continue; if (pw[i - 1] == '0') continue; x = (pw[i - 1] - '0') * 10 + (pw[i] - '0'); if (10 <= x && x <= 26) { d[i] += d[i - 2]; d[i] %= 1000000; } } printf("%d\n", d[len]); return 0; } |
'Algorithm > Problem Solving' 카테고리의 다른 글
[BOJ/2609] 최대공약수와 최소공배수 (0) | 2020.04.23 |
---|---|
[BOJ/10430] 나머지 (0) | 2020.04.22 |
[BOJ/2225] 합분해 (0) | 2020.04.22 |
[BOJ/9461] 파도반 수열 (0) | 2020.04.22 |
[BOJ/2133] 타일 채우기 (0) | 2020.04.22 |