[ BOJ/C# ] 9461 파도반 수열

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

9461번: 파도반 수열

다이나믹 프로그래밍 문제이다. 

문제 자체에 케이스도 많이 보여주었기 때문에 쉽게 풀 수 있는 문제였다. 

다만, 처음 제출이 틀렸다. DP가 틀렸을 거라는 생각을 안 했기 때문에 반례를 찾으려 뒤의 숫자들을 넣어봤다. 

100까지밖에 안했기 때문에, 100 가까이 넣어보니 음수로 출력되었다. (오버플로우)

이 문제를 해결하기 위해 dp배열의 자료형을 int 대신 long으로 바꿔주었더니 해결되었다. 

using System;
using System.Text;

namespace B9461
{
    class Program
    {
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();

            int t = int.Parse(sr.ReadLine());
            long[] dp = new long[101];
            int index = 3;
            for (int i = 1; i <= 3; i++) dp[i] = 1;
            for(int i = 0; i < t; i++)
            {
                int n = int.Parse(sr.ReadLine());
                if (n > index)
                {
                    for(int j = index + 1; j <= n; j++)
                        dp[j] = dp[j - 2] + dp[j - 3];
                    index = n;
                }
                sb.Append(dp[n] + "\n");
            }
            sw.Write(sb);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}

자료형을 바꿔주기 전

자료형을 long으로 바꾼 후