백준 2011 암호코드(dynamic programming)

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

2011번: 암호코드

#include <iostream>

using namespace std;

const int MAX = 5001;
const int MOD = 1000000;
int dp[MAX];
int arr[MAX];
int N;

void decoding()
{
    dp[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        if (arr[i] >= 1 && arr[i] <= 9)
            dp[i] = (dp[i]+dp[i - 1]) % MOD;
        if (i == 1)
            continue;
        int num = arr[i - 1] * 10 + arr[i];
        if (num >= 10 && num <= 26)
            dp[i] = (dp[i]+dp[i - 2]) % MOD;
    }
    cout << dp[N];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string tmp;
    cin >> tmp;
    N = tmp.length();
    for (int i = 1; i <= N; i++)
    {
        arr[i] = tmp[i - 1] - '0';
    }
    if (tmp[0] == 0 && N == 1)
    {
        cout << 0;
    }
    else
    decoding();
}

이래저래 좀 까다로운 문제였다...

 

가장 먼저 지금까지 본 dp문제들은

for(int i=1;i<=N;i++){
	for(int j=1;j<=N;j++){
    
    }
} 

//1차원 배열의 경우

 

for(int i-1;i<=N;i++){
	for(int j=1;j<=M;j++){
    
    }
}
//NxM의 2차원 배열의 경우

와 같은 기본 모양으로 다 풀 수 있었다.

 

이 문제도 물론 이런 모양으로 어떻게든 풀려면 풀었겠지만 답안에 적어놓은 형태로 푸는 것이 가장 쉽고 간단했다.

저런 모양도 있을 수 있다는 것을 기억하자.

 

점화식은 사실 굉장히 간단한 편이라 문제를 한번 읽고 코드를 본다면 쉽게 이해할 수 있을 것 같다.

 

까다로웠던 부분은 특히 2 부분이었다.

 

int num = arr[i - 1] * 10 + arr[i];
        if (num >= 10 && num <= 26)
            dp[i] = (dp[i]+dp[i - 2]) % MOD;
    }

처음에 이 부분을

if (arr[i-1]>0 && arr[i-1]<=2 && arr[i] <= 6)
    dp[i] = (dp[i]+dp[i - 2]) % MOD;
}

이렇게 해서 계속 틀려버렸다.

조금만 생각해보면 이런 식으로 짜게 되면 10~26이 아닌 10~16,20~26이 된다는 것을 알 수 있는데 이것 때문에 꽤 많은 시간을 허비했다.

 

두번째로는 이 부분이다.

dp[i] += (dp[i - 1]) % MOD;
dp[i] = (dp[i]+dp[i - 1]) % MOD;

나는 처음에 이 두 줄이 똑같은 의미를 가진다 생각했다. 하지만, 연산자 우선순위를 제대로 파악하지 못해 일어난 참사였다...

 

+=, -=와 같은 대입 연산자들은 %보다 훨씬 낮은 우선순위를 가진다. 이 때문에 dp[i]와 dp[i-1]이 더해져서 %연산이 수행되는 것이 아닌 dp[i-1]만 %연산 처리 되고 그 이후에 dp[i]가 더해지는 잘못된 일이 발생한 것이었다. 다음부터는 주의해야겠다.