문제

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

풀이

원래 통과되었던 코드가 테스트 추가로 재채점 되면서 오답 처리로 바뀌었다. 그래서 새 문제를 푸는 마음으로 기존의 코드를 참고하지 않고 다시 코드를 작성해보았다.

A를 1, Z를 26이라 하고 5000자리 이하의 수가 주어졌을때 수를 다시 영문 문자열로 바꿀수 있는 모든 경우의 수를 구하는 것이 문제이다. 5000자리 이하이므로 문자열로 값을 받아야한다.

정상적으로 문자열로 변환이 가능한 경우는 아래와 같다.

현재 한 자리만 볼 때

  • 현재 수가 1~9인가?
    • 별 다른 문제 없이 정상적인 문자열을 만들 수 있다.

두 자리를 볼 때

  • 현재 수가 1인가?
    • 다음에 어떤 숫자가 오는지 상관없이 문자열을 만들 수 있다.
  • 현재 수가 2인가?
    • 다음 수가 반드시 0 ~ 6 사이어야한다.

예를 들어 61… 같은 경우는 (6, 1, …)처럼 한 자리씩 자를 수 있는 경우밖에 없지만, 24…는 (2, 4, …)와 (24, …) 두 가지 경우를 모두 포함시켜야한다.

메모이제이션은 아래와 같이 하면 된다.

dp[x] = x번째 자리에서 시작하여 문자열을 만들 수 있는 경우의 수

코드

#include <stdio.h>
#include <string.h>
#define MOD 1000000
#define max(x,y) x>y?x:y

int len, dp[5001];
char arr[5001];

int solve(int pos){
    int ret = 0;
    if(pos == len) return 1;
    if(dp[pos] != -1) return dp[pos];
    if(arr[pos] == '0') return dp[pos] = 0;
    ret = (ret + solve(pos+1)) % MOD;
    if(pos + 1 < len){
        if(arr[pos] == '1')
            ret = (ret + solve(pos+2)) % MOD;
        else if(arr[pos] == '2' && arr[pos + 1] <= '6')
            ret = (ret + solve(pos+2)) % MOD;
    }
    return dp[pos] = ret;
}
int main(){
    scanf("%s",arr);
    len = strlen(arr);
    memset(dp,-1,sizeof(dp));
    printf("%d",solve(0));
}