문제

문제 링크

문제 접근

  • 이 문제는 전형적인 디피 문제의 냄새가 났다.
  • 이차원 어레이를 사용하면 풀 수 있을 것 같아 보여서 나름의 원리를 만들고 돌려보니 정답이 나오는 것을 확인할 수 있었다.

주의할 점

  • 0이 들어오는 경우를 한번 잘 생각해봐야 한다.

코드

#include <cstdio>
int arr[5001][2], num, nxt, p, n;
char s[5001];
int main(){
    scanf("%s", s);
    p = s[0] - '0';
    if(p != 0)arr[0][0] = 1;
    for(int i = 1; s[i] != '\0'; i++){
        n++;
        num = s[i] - '0';
        if(num)arr[i][0] = (arr[i-1][0]+arr[i-1][1]) % 1000000;
        nxt = p * 10 + num; 
        if(!nxt)break;
        if(nxt > 9 && nxt < 27)arr[i][1] = arr[i-1][0] % 1000000;
        p = num;
    }
    printf("%d", (arr[n][0] + arr[n][1]) % 1000000);
}

느낀점

  • dp로 수월하게 끝내버린 문제였다!