Algorithm/Problem Solving 2020. 4. 22. 23:04

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

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

 

사용 알고리즘

- DP

 

풀이

- d[i] = i번째 문자까지 해석했을 때 나올 수 있는 해석의 가짓수

- i - 1과 i를 붙였을 때 10 ~ 26인 경우, 

  d[i] = d[i - 1] + d[i - 2]

- i - 1과 i를 붙였을 때 10 ~ 26이 아닌 경우,

  d[i] = d[i - 1]

 

소스 코드

https://github.com/moomini/algorithm/blob/master/boj/2011.cpp

#include <cstdio>

#include <cstring>

 

int d[5003];

 

int main(void) {

    char pw[5003]; scanf("%s", pw + 1);

    int len = strlen(pw + 1);

    d[0= 1;

    for (int i = 1; i <= len; ++i) {

        int x = pw[i] - '0';

        if (1 <= x && x <= 9) d[i] += d[i - 1];

        if (i == 1continue;

        if (pw[i - 1== '0'continue;

        x = (pw[i - 1- '0'* 10 + (pw[i] - '0');

        if (10 <= x && x <= 26) {

            d[i] += d[i - 2];

            d[i] %= 1000000;

        }

    }

    printf("%d\n", d[len]);

    return 0;

}

Colored by Color Scripter

cs

 

'Algorithm > Problem Solving' 카테고리의 다른 글

[BOJ/2609] 최대공약수와 최소공배수  (0) 2020.04.23
[BOJ/10430] 나머지  (0) 2020.04.22
[BOJ/2225] 합분해  (0) 2020.04.22
[BOJ/9461] 파도반 수열  (0) 2020.04.22
[BOJ/2133] 타일 채우기  (0) 2020.04.22
posted by DevMoomin
: