글 읽기 - 2011 암호 도와주세요

khwbori 7년 전 0

dp로 풀어봤습니다.

예를들어

200114 이면 0이나 00 은 해석할 수 없는 수이기 때문에 답은 0 으로 했습니다.

01234 역시 답은 0으로 했습니다.

30114 역시 답은 0으로 했습니다.

어떤 케이스에서 틀린것일까요..?

#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

string inputs;

int solv(int n){
    int dp[5005];
    dp[0]=1;
    dp[1]=1;
    for(int i=2; i<=n; i++){
        //0으로 시작하거나 00 이 나오면 해석할수 없으므로 0 return
        if((inputs[i-2]=='0' && inputs[i-1]=='0')||inputs[0]=='0'){
            break;
        }
        //26이하이고 20이나 30 이 아니면 경우의 수는 숫자1개로 만든 단어 + 숫자 2개로 만든단어
        if( ((inputs[i-2]-'0')*10 +(inputs[i-1])-'0')<=26 && ((inputs[i-2]-'0')*10 +(inputs[i-1])-'0')%10 != 0){
          
            dp[i]=(dp[i-1]+dp[i-2])%1000000;
        }else{
            if(((inputs[i-2]-'0')*10 +(inputs[i-1])-'0')%10 == 0)
            {
              //30,40은 해석할 수 없는 숫자이므로 0return
              if(((inputs[i-2]-'0')*10 +(inputs[i-1])-'0')>20){break;}
              dp[i]=dp[i-1]%1000000;
              dp[i-1]=0;
            }
            else
            dp[i]=dp[i-1]%1000000;
        }
    }
    return dp[n];
}

int main(void){
   
    cin >> inputs;
    
    int ret = solv(inputs.length());
    printf("%d\n",ret);
    return 0;
}

zlzmsrhak 7년 전 1

반례입니다.

110

답: 1

khwbori 7년 전 0

감사합니다^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2011 암호 도와주세요

khwbori 7년 전 0

zlzmsrhak 7년 전 1

khwbori 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말