[알고리즘 문제 풀기] 알약(4811)

1. 문제 풀이 아이디어

• DP를 사용하여 남은 완전한 약과 반 조각의 개수에 따라 가능한 문자열의 개수를 구한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    long[,] dp = new long[31, 31];
    for (int i = 0; i <= 30; i++)
    {
        for (int j = 0; j <= 30; j++)
        {
            if (i == 0) dp[i, j] = 1;
            else dp[i, j] = (j < 30 ? dp[i - 1, j + 1] : 0) + (j > 0 ? dp[i, j - 1] : 0);
        }
    }

    int n;
    while ((n = int.Parse(sr.ReadLine())) != 0)
    {
        sw.WriteLine(dp[n, 0]);
    }
}

3. 정리

• DP 배열 dp[i, j]는 i개의 완전한 약과 j개의 반 조각이 남아있을 때 가능한 문자열 개수를 저장한다.

• 완전한 약을 꺼내면 dp[i-1, j+1]을 더하고, 반 조각을 꺼내면 dp[i, j-1]을 더하는 방식으로 점화식을 적용한다.

• 입력된 n에 대해 dp[n, 0] 값을 출력하여 가능한 문자열의 개수를 구한다.