https://www.acmicpc.net/problem/2011
2011번: 암호코드
나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.
www.acmicpc.net
[난이도] Gold5
[유형] DP
[풀이]
DP[i] : s가 길이 n인 암호 문자열일 때, s[i..n-1] 로 만들 수 있는 해석의 총 개수.
#include <string> #include <iostream> #include <cstring> using namespace std; int dp[5001]; string s; int sol(int n){ if(n>=s.size()) return 1; int& ret = dp[n]; if(ret!=-1) return ret; if(s[n]=='0') return 0; ret=sol(n+1); if(n+1<s.size()){ int k = (s[n]-'0')*10+(s[n+1]-'0'); if(k<27) ret=(ret+sol(n+2))%1000000; } return ret; } int main(){ cin >> s; memset(dp,-1,sizeof(dp)); cout << sol(0); }
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2011.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold5] 1106 : 호텔 (C++) (0) | 2022.05.29 |
|---|---|
| [BOJ/백준][Gold5] 19940 : 피자 오븐 (C++) (0) | 2022.05.13 |
| [BOJ/백준][Gold1] 1509 : 팰린드롬 분할 (C++) (0) | 2022.05.13 |
| [BOJ/백준][Gold5] 19942 : 다이어트 (C++) (1) | 2022.05.13 |
| [BOJ/백준][Platinum5] 2568 : 전깃줄 - 2 (C++) (0) | 2022.05.13 |