백준의 암호코드(2011) 문제이다.
[ 문제 바로가기 ]
[ 문제풀이 ]
1) 주어진 숫자를 영어로 바꿔서 해석할 때, 총 몇가지로 해석할 수 있는지를 구하는 문제이다. 먼저 본인은 문제를 해결하기
위해서 DP[] int형 배열을 하나 사용해주었다.
DP[a] = b 의 의미는 "a번째 숫자까지 읽을 수 있는 단어의 갯수는 b개입니다" 이다.
쉬운 예로 문제가 돌아가는 형식을 이해하고, 자연스럽게 점화식을 도출해보자.
"1234" 라는 숫자가 있다.
먼저, DP[1]의 값을 얼마일까?? 아마 1일 것이다. 왜냐하면, 1번째 숫자까지 읽을 수 있는 단어의 갯수는 1을 영어로 바꾼
'A' 한개만 존재하기 때문이다. 1보다 이전에 존재하는 숫자도 없기 때문에 'A'한개만 읽을 수 있으므로 DP[1] = 1이다.
그렇다면 2로 가보자.
2같은 경우에는, 2가지 경우로 갈리게 된다.
1. 앞에 숫자인 '1'을 A로 읽고, '2'를 B로 읽어서 "AB"라는 단어를 만드는 경우.
2. 앞에 숫자와 합쳐서 '12' 를 "L"로 읽는 경우
이렇게 2가지 경우가 있다.
1번의 경우는 어떻게 계산을 해줘야 할까?? DP[1]의 값에다가 DP[2]의 값을 더해주면 된다.
초기값으로 DP[2] = 0으로 설정되어 있을 것이다. DP[1]의 값에다가 + DP[2]를 해주면 1 + 0 = 1 로 1이 된다.
이렇게 계산해주는 이유를 알아보자.
저 값이 DP[2]가 아닌 DP[200] 이라고 생각을 해보자. DP[200]인 경우에, 199번째 값을 A로 따로 읽고, 200번째 값을 B로
따로 읽는 경우라고 생각을 해보자. 이 경우에는, 199번째 숫자까지 읽을 수 있는 단어의 갯수 + DP[200]이 된다.
물론 이 식을 충족하기 위해서는 DP[0] = 1이라는 초기조건이 필요하다.
다시 처음으로 돌아와서 DP[1]을 다시 계산해보자. DP[1]의 경우, DP[2]를 계산한것과 같이 계산한다면
0번째 단어까지 읽을 수 있는 단어의 갯수 + DP[1]이라는 이야기인데, 0번째 단어까지 읽을 수 있는 단어의 갯수라는 말 자체가
모순적이다. 하지만, 이 식을 위해서 DP[0] = 1이라는 초기값을 설정해주면, DP[1] = 1 이라는 결과를 얻어낼 수 있다.
2번의 경우는 어떻게 계산을 해줄까?? 2번의 경우도 1번과 똑같다. 1번에서는 자기 이전의 숫자를 다른 단어로 취급하였지만,
이번에는 하나의 단어로 취급을 해줘야 한다. 위에서 말했듯이, 200번째 단어라고 생각해보면, 198번째까지 읽을 수 있는
단어의 갯수 + DP[200]이 된다.
즉, 점화식을 도출해내자면...
DP[A] = DP[A-1] + DP[A]
DP[A] = DP[A-2] + DP[A] 이렇게 2개의 식이 성립된다.
물론, 조건이 붙어야 한다.
DP[A] = DP[A-1] + DP[A] 라는 식에는, Arr[A]의 값이 1 ~ 9 사이여야만 하고,
DP[A] = DP[A-2] + DP[A] 라는 식에는, A가 1번째 단어가 아니고, Arr[A-1] * 10 + Arr[A]를 한 값이, 10 ~ 26 (알파벳범위) 여야
한다는 조건이 붙어야 한다.
[ 소스코드 ]
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include<iostream> #include<string> #define endl "\n" #define MAX 5000 #define Moduler 1000000 using namespace std; int Arr[MAX]; int DP[MAX] , Len; string Inp; void Input() { cin >> Inp; Len = Inp.length(); for (int i = 1; i <= Len; i++) { Arr[i] = Inp[i - 1] - '0'; } } void Solution() { if (Len == 1 && Inp[0] == '0') { cout << 0 << endl; exit(0); } DP[0] = 1; for (int i = 1; i <= Len; i++) { if (Arr[i] >= 1 && Arr[i] <= 9) { DP[i] = (DP[i - 1] + DP[i]) % Moduler; } if (i == 1) continue; int Temp = Arr[i] + Arr[i - 1] * 10; if (Temp >= 10 && Temp <= 26) { DP[i] = (DP[i - 2] + DP[i]) % Moduler; } } //for (int i = 1; i < Len; i++) //{ // cout << "DP[" << i << "] = " << DP[i] << endl; //} cout << DP[Len] << endl; } void Solve() { Input(); Solution(); } int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("Input.txt", "r", stdin); Solve(); return 0; } | cs |
'[ BOJ Code ] > # BOJ -' 카테고리의 다른 글
[ 백준 9177 ] 단어 섞기 (C++) (0) | 2019.02.12 |
---|---|
[ 백준 3407 ] 맹세 (C++) (0) | 2019.02.11 |
[ 백준 1213 ] 팰린드롬 만들기 (C++) (0) | 2019.02.11 |
[ 백준 16235 ] 나무 재테크 (C++) (10) | 2019.02.10 |
[ 백준 16236 ] 아기 상어 (C++) (2) | 2019.02.10 |