[알고리즘 문제 풀기] 1, 2, 3 더하기 4(15989)

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[] n = new int[t];
    int max = 3;
    for (int i = 0; i < t; i++)
    {
        n[i] = int.Parse(sr.ReadLine());
        max = Math.Max(max, n[i]);
    }
    int[,] dp = new int[max + 1, 2];
    dp[2, 0] = 1;
    dp[3, 0] = 1;
    dp[3, 1] = 1;
    for (int i = 4; i <= max; i++)
    {
        dp[i, 0] = dp[i - 2, 0] + 1;
        dp[i, 1] = dp[i - 3, 0] + dp[i - 3, 1] + 1;
    }
    for (int i = 0; i < t; i++)
    {
        sb.AppendLine((dp[n[i], 0] + dp[n[i], 1] + 1).ToString());
    }
    sw.Write(sb);
}

3. 정리

• 입력값 중 최댓값을 찾아 DP 테이블을 미리 채운다.

• dp[i, 0]은 i에서 2를 빼는 경우의 수를, dp[i, 1]은 i에서 3을 빼는 경우의 수를 저장한다.

• 각 테스트 케이스마다 사전 계산된 값을 활용하여 빠르게 정답을 출력한다.