[C] 백준 | 12037번 코드 - Polynesiaglot

>문제

www.acmicpc.net/problem/12037

12037번: Polynesiaglot (Small1)

> 핵심

DP

자음 앞에는 모음만 올 수 있다

>풀이과정

와 어렵다

다이나믹 프로그래밍 기법을 사용하지만 내 머리는 다이나믹하게 돌아가지 않는다

 

몇시간동안 끙끙대서 겨우 풀었다

 

근데 막상 풀고나니까 코드는 그닥 길지도 않다. 시부랑탱

 

역경의 흔적..

 

그렇게 찾은 수식..

 

모음으로 끝나는 경우 -> 다음에는 모음 / 자음 두가지 경우가 올 수 있다

( aa -> haa, aaa )

자음으로 끝나는 경우 -> 다음에는 모음 한가지경우만 올 수 있다.

( ha -> aha )

 

그니까 모음으로 끝나는 경우를 구하기 위해서는

이전 단어가 모음인 경우에 V가지 경우를 곱, dp[i-1][0] * V

이전 단어가 자음인 경우에 V가지 경우를 곱, dp[i-1][1] * V

두개를 더해서 구할 수 있다. dp[i][0] = V * (dp[i-1][0] + dp[i-1][1])

 

자음으로 끝나는 경우를 구하기 위해서는,

이전 단어가 모음인 경우에 C가지 경우를 곱, dp[i-1][0] * C

만을 고려하면 된다. dp[i][1] = C * dp[i-1][0]

 

이거 찾아서 두개 합하면 된다..

 

그리고 반복문 돌때마다 dp 배열을 초기화 해줘야 코드가 돌아간다!!

이거 안해서 또 뻘짓했다..

 

======

추가

연관문제인 12038, 12039번 문제는 int형을 long long 형으로 바꾸고 나머지 연산만 꼬박꼬박 하면 정답이 된다

www.acmicpc.net/problem/12039

12039번: Polynesiaglot (Large)

 

>깨달은점

막상 글로 정리하니까 어렵지 않은 구조인듯 한데

왜이렇게 오래걸렸나 모르겠다. 아무래도 이런 문제에 익숙하지 않다는 점이 가장 클 것 같다..

좀 코딩할때 차분한 마음으로 접근할 필요가 있을 것 같다. 자꾸 해결이 안되면 때려치고싶어진다..

 

반복문으로 돌렸으면 진작에 풀었을 것 같은데 dp로 생각하려니까 더 머리가 터지겠다

근데 dp는 알고리즘에서 절대 빼놓을 수 없는 파트라고 한다.

앞날이 막막하다

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define SIZE 16

int dp[SIZE][2];

void init_dp()
{
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            dp[i][j] = 0;
        }
    }
}

int calc(int C, int V, int L)
{
    // 모음으로 끝나는 경우
    dp[0][0] = V;

    // 자음으로 끝나는 경우
    dp[0][1] = 0;

    if (dp[L][0] != 0) return dp[L][0];

    for (int i = 1; i <= L; i++)
    {
        // 모음으로 끝나는 경우 -> 앞이 자음 혹은 모음
        dp[i][0] = dp[i - 1][0] * V + dp[i - 1][1] * V % 1000000007;

        // 자음으로 끝나는 경우 -> 앞이 모음
        dp[i][1] = dp[i - 1][0] * C % 1000000007;
    }

    return (dp[L][0] + dp[L][1]) % 1000000007;
}

int main()
{
    int T, C, V, L, i, e;
    scanf("%d", &T);

    for (i = 0; i < T; i++)
    {
        scanf(" %d %d %d", &C, &V, &L);
        e = calc(C, V, L - 1);
        printf("Case #%d: %d\n", i + 1, e);
        init_dp();
    }

    return 0;
}

 

+)12038, 12039번 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define SIZE 501

long long dp[SIZE][2];

void init_dp()
{
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            dp[i][j] = 0;
        }
    }
}

long long calc(int C, int V, int L)
{
    // 모음으로 끝나는 경우
    dp[0][0] = V;

    // 자음으로 끝나는 경우
    dp[0][1] = 0;

    if (dp[L][0] != 0) return dp[L][0];

    for (int i = 1; i <= L; i++)
    {
        // 모음으로 끝나는 경우 -> 앞이 자음 혹은 모음
        dp[i][0] = V * (dp[i - 1][0] + dp[i - 1][1]);
        dp[i][0] %= 1000000007;

        // 자음으로 끝나는 경우 -> 앞이 모음
        dp[i][1] = (dp[i - 1][0]) * C;
        dp[i][1] %= 1000000007;
    }

    return (dp[L][0] + dp[L][1]);
}

int main()
{
    int T, C, V, L, i;
    long long e;
    scanf("%d", &T);

    for (i = 0; i < T; i++)
    {
        scanf(" %d %d %d", &C, &V, &L);
        e = calc(C, V, L - 1);
        printf("Case #%d: %lld\n", i + 1, e % 1000000007);
        init_dp();
    }

    return 0;
}