[알고리즘 문제 풀기] Ezreal 여눈부터 가네 ㅈㅈ(20500)

1. 문제 풀이 아이디어

• DP를 사용하여 수열을 구하고, 나머지 연산을 적용하여 값을 계산해 문제를 해결한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    // 0 1 1 3 5 11 21 43 85
    int n = int.Parse(sr.ReadLine());
    long[] dp = new long[n + 1];
    dp[1] = 1;
    for (int i = 2; i < n; i++)
    {
        dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 1000000007;
    }
    sw.WriteLine(dp[n - 1]);
}

3. 정리

• dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 1000000007를 사용하여 점화식을 구현한다.

• dp 배열을 생성하여 값을 저장하며 중복 계산을 방지한다.

• n을 입력받고 dp[n-1] 값을 출력하여 결과를 구한다.