[백준 2011] 암호코드

www.acmicpc.net/problem/2011

2011번: 암호코드

DP를 사용하는 문제이며 리트코드에서도 유사한 문제를 푼 경험이 있다.

 

DP[i]는 i번째 숫자를 포한해서 만들 수 있는 암호코드 최대 갯수로 정의한다.

 

dp[i]에 영향을 주는 요소는 dp[i-1]과 dp[i-2]가 있다.

25114의 경우

2 -> B

25 -> B + E / ' ' +Y 

251 -> BE + A / Y + A 

2511 -> BEA + A / YA + A / BE + K / YA + K

25114 -> BEAA + D / YAA + D / BEK + D / YAK + D / BEA + N / YA + N

이렇게 암호코드를 만들 수 있다. 현재 숫자로 암호를 만들 수 있다면 (code[i] 가 1에서 9사이) 이전 dp[i-1]값을 더하고

현재숫자와 이전 숫자로 암호를 만들 수 있다면( code[i-1] code[i]가 10에서 26사이) dp[i-2]도 더해준다.

 

dp[1]의 경우 무조건 1이므로 dp[0] = 1로 설정해준다.

#include <stdio.h>
#include <string.h>

using namespace std;

char code[5001];
int dp[5001];
int main(void)
{
  scanf("%s", code);
  int len = strlen(code);
  dp[0] = 1;
  for (int i = 0; i < len; i++)
  {
    int j = i + 1;

    int cur = code[i] - '0';
    //printf("%d ", cur);
    if (cur < 0)
    {
      break;
    }

    if (cur >= 1 && cur <= 9)
    {

      dp[j] += dp[j - 1];
    }

    if (i > 0)
    {
      cur += (code[i - 1] - '0') * 10;
      if (cur >= 10 && cur <= 26)
      {
        dp[j] += dp[j - 2];
      }
    }

    //printf("%d ", cur);
    dp[j] %= 1000000;
    //printf("%d\n", dp[j]);
  }

  printf("%d\n", dp[len]);
  return 0;
}