[BOJ/백준 2011][C++] 암호코드

문제

https://www.acmicpc.net/problem/2011

백준 2011

 

문제 내용

A~Z까지의 알파벳을 1~26으로 각각 매칭 해두고 암호화를 진행했다.

숫자로 이루어진 암호가 주어질 때, 이를 해석하고자 한다.

해석할 수 있는 가짓수를 출력하면 된다.

(정답이 매우 클 수 있으므로, 1,000,000으로 나눈 나머지를 출력한다.)

 

문제 풀이

dp문제이다.

일단 가장 첫 숫자가 0이라면 암호 자체가 잘못되었기 때문에 0을 반환한다.

 

dp[a]=b라고 쓰면 a번째까지 해석할 수 있는 가짓수가 b 개라는 뜻이다.

dp[1]=1이다.

왜냐하면, 1번째 숫자까지 읽을 수 있는 단어의  개수는 1개이기 때문이다.

(1이라면 A, 2라면 B... 9라면 I가 된다.)

 

그럼 dp[2]는 얼마일까?

이때부터는 고려사항이 늘어난다.

"1342"라는 예시를 기준으로 보면 dp[2]=2가 된다.

{1,3} => AC / {13}=> M 이렇게 두 가지 경우가 된다.

"3124"의 경우는 어떻게 될까?

이 경우는 dp[2]=1이 된다.

{3,1}=CA는 가능하지만, {31}은 1~26의 범위를 벗어나기 때문이다.

 

그럼 이제 dp 수식을 짜 보겠다.

먼저 한 글자로만 읽는다고 생각하고 dp배열을 초기화해주면 된다.

그렇다면  dp[i]=dp[i-1]% MOD가 된다. 

dp[i]=(dp[i]+dp[i-1])%MOD로 적어도 된다.

 

그 이후에, 두 자리를 고려한다.

(code[i-2]-'0')*10+(code[i-1]-'0') 라는 식을 통해 2자리 숫자를 구한다.

(입력을 숫자처럼 보여도 문자열로 받았기 때문이다.)

그리고 구한 숫자가 1~26 사이에 해당하면 dp배열에 가짓수를 추가해주면 된다.

그럼 dp[i]=(dp[i]+dp[i-2])%MOD의 식을 구할 수 있다.

 

i-1번째 글자와 i번째 글자를 합쳐 암호를 해석했기 때문에, i-2번째까지의 가짓수를 dp[i]에 더해주어야 하는 것이다.

 

코드

#include <iostream>
#include <vector>

using namespace std;
const int MOD = 1e6; //모듈러 연산 상수
int dp[5001]={0,};
int solution(string code, int n ) {
	if(code[0]=='0') return 0;
	dp[0]=dp[1]=1;
	
	for(int i=2;i<=n;i++){
		if(code[i-1]!='0') dp[i]=dp[i-1]%MOD;
		
		int tmp=(code[i-2]-'0')*10+(code[i-1]-'0');
		if(tmp>=10&&tmp<=26)
			dp[i]=(dp[i]+dp[i-2])%MOD;
	}

    return dp[n];
}

int main() {
    string str;  
    cin >> str;   
    int answer = solution(str, str.length());  
    cout << answer;
    return 0;
}