5. DP
[DP] 백준 2011번 - 암호코드
asdklfjlasdlfkj
2020. 1. 29. 15:50
https://www.acmicpc.net/problem/2011
2011번: 암호코드
문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "
www.acmicpc.net
백준 DP문제다.
n번째 자리까지 가질 수 있는 경우의 수를 dp[n]에 저장하면
dp[string.length()]를 구해 출력하면 된다.
이 때 입력한 string의 i번째는 string[i-1]에 저장되어 있는데, 이 값을 갖고
i) 1~9사이 값일 경우 dp[i]에 이전 자리까지 만들 수 있는 경우의 수를 더해준다. (dp[i] += dp[i-1];)
ii) 또한 string[i-2]*10 + string[i-1] 값이 10~26사이 값일 경우 역시 dp[i] += dp[i-2];를 해준다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <iostream>
#include <string>
#define mod 1000000
using namespace std;
int dp[5001];
// dp[n] : n번째 까지 가질 수 있는 경우의 수
// 1자리인경우, 2자리인경우
int main(){
string s;
cin >> s;
dp[0] = 1;
for (int i = 1; i <= s.length(); i++){
int x = s[i - 1] - '0';
if (x >= 1 && x <= 9){
dp[i] += dp[i - 1];
dp[i] %= mod;
}
if (i == 1) continue;
x = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
if (10 <= x && x <= 26){
dp[i] += dp[i - 2];
dp[i] %= mod;
}
}
cout << dp[s.length()] << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |