[Algorithm] Baekjoon 2011번 : 암호코드

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

2011번: 암호코드

#define MOD 1000000;
 
string code = "";
int targetSize = 0;
int dp[5001];
 
 
int DFS(int curIndex)
{
    if (curIndex == targetSize) return 1; // 완성.
    if (dp[curIndex] != 0x3f3f3f3f) return dp[curIndex] % MOD;
 
    dp[curIndex] = 0;
 
    if (code[curIndex] - '0' > 0)
    {
        dp[curIndex] = (dp[curIndex] + DFS(curIndex + 1)) % MOD;
    }
 
    if (targetSize - curIndex - 1 >= 1)
    {
        string temp = code.substr(curIndex, 2);
        int num = stoi(temp);
 
        if (num >= 10 && num <= 26)
        {
            dp[curIndex] = (dp[curIndex] + DFS(curIndex + 2)) % MOD;
        }
 
    }
 
    return dp[curIndex] % MOD;
}
 
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> code;
 
    targetSize = code.size();
    memset(dp, 0x3f, sizeof(dp));
 
 
    DFS(0);
 
    cout << dp[0] % MOD;
}
 

풀고 상당히 뿌듯한 문제.

정답비율이 19%대인 문제인데, 95%는 자력으로 풀어서 그래도 실력이 좀 늘었구나.. 생각했다.

5%는 '07' 같은경우 케이스를 고려안했기 때문에... 다른 사람 테스트케이스를 보고 아차 싶어서 반영했다.

 

여느 DP문제와 같이 문제를 재해석하는게 중요하다.

이 문제는 결국 1과 2를 이용해서 암호코드의 길이만큼의 숫자를 만드는 경우의 수를 뽑는 문제다.

뭔 소린가? 하면 결국 암호코드는 1개씩 쪼개거나 2개씩 쪼갠다. 

즉 암호코드의 총 길이가 5라면

 

1, 1, 1, 1, 1로 쪼개거나

1, 1, 1, 2 로 쪼개거나

1, 2, 1, 1 로 쪼개거나 한다.

 

대충 감이 올 수도 있다. 1과 2를 조합해서 5를 만드는 형태랑 상당히 비슷하다.

좀 더 디테일한 조건으로는 갯수는 상관 없으며, (어차피 최대 암호코드갯수겠지만)

순서가 다른 경우도 각각의 경우의 수로 친다. (1 + 2와 2 +1은 따로 카운팅한다)

 

그래서 DFS를 통해 +1씩 전진하거나 +2씩 전진하며 탐색한다.

 

여기서 +1로 전진하기 위해 조건이 있다 (처음에 없는줄 알고 그냥 했다가 '0'이 있다는걸 깜박했다.)

알파벳 A~Z를 1~26으로 치환하는것이기 때문에, 현재 값이 0일 때는 더이상 전진할 수 없다.

한 자리의 수는 1~9일때만 전진이 가능하다는것을 알아야한다.

 

+2로 전진하기 위해서는 1과 마찬가지로 적절한 값이여야 한다.

현재 2글자짜리 문자열이 '07'이라면 적절하지 않는 값이다.

처음에 말했던 것처럼, 07 같은 경우를 고려하지 않고 그냥 int로 형변환 후, 26이하인 값이면 탐색을 진행하게 했더니 15%대에서 실패가 떠서 다른 테스트케이스를 찾아봤었다.

아마 15%대 테스트케이스가 딱 0이 포함된 테스트케이스인가보다.

 

어쨌든 '07'같은 경우가 있으니, 무작정 26이하로 조건처리하지말고 10이상의 조건도 추가하던지 해서 조건을 잘 걸고 탐색을 진행해야 한다.

 

그리고 MOD연산 해줘야하는 조건이 있으니 잊지말아야 한다.