[알고리즘 문제 풀기] 인접한 비트의 개수(2698)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 활용하여 길이와 인접한 1의 개수, 마지막 비트(0 또는 1)에 따른 경우의 수를 누적하여 계산해 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;

StringBuilder sb = new StringBuilder("");

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int t = int.Parse(sr.ReadLine());
    int[,,] dp = new int[101, 101, 2];
    dp[1, 0, 0] = 1;
    dp[1, 0, 1] = 1;
    for (int i = 2; i < 101; i++)
    {
        for (int j = 0; j < 101; j++)
        {
            dp[i, j, 0] = dp[i - 1, j, 0] + dp[i - 1, j, 1];
            dp[i, j, 1] = dp[i - 1, j, 0] + (j > 0 ? dp[i - 1, j - 1, 1] : 0);
        }
    }
    while (t > 0)
    {
        string[] split = sr.ReadLine().Split();
        int n = int.Parse(split[0]);
        int k = int.Parse(split[1]);
        sb.AppendLine((dp[n, k, 0] + dp[n, k, 1]).ToString());
        t--;
    }
    sw.Write(sb);
}

3. 정리

• dp[i, j, 0]은 i번째에 0이 오는 경우로, 이전에 0 또는 1이 오는 경우 모두 가능하므로 둘을 더한다.

• dp[i, j, 1]은 i번째에 1이 오는 경우로, 이전에 0이 오면 j는 그대로이고, 이전에 1이 오면 인접한 1이 생기므로 j-1을 더한다.

• dp[n, k, 0] + dp[n, k, 1]이 최종 정답이다.