2022.02.06 [백준] C# 01타일

 

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

1904번: 01타일

 

---

풀이

이 문제는 규칙을 적어보면 피보나치 수열과 같다. f(n)=f(n-1)+f(n-2)

 

아래의 코드는 메모이제이션을 이용한 Top-down방식을 이용하여 작성했다. 다음의 코드로 작성했을 때 시간 초과가 발생하였다.

 

-시간 초과 코드

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[] cnt;
    static int func(int n)
    {
        if (n == 1)
        {
            cnt[1] = 1;
            return 1;
        }
        if (n == 2)
        {
            cnt[2] = 2;
            return 2;
        }
        cnt[n] = (func(n - 1) + func(n - 2))%15746;
        return cnt[n];
    }
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        cnt = new int[1000001];
        int n = int.Parse(sr.ReadLine());
        func(n);
        sw.WriteLine(cnt[n]);
        sr.Close();
        sw.Close();
    } 
}

 

위의 방식으로 코드를 작성했을 때 시간초과가 발생하여 메모이제이션으로 이전 계산식을 저장하며 Bottom-up방식으로 코드를 작성하였더니 해결할 수 있었다.

처음 제출했을 때 코드가 틀렸다고 해서 엄청 고민하다가 문제를 잘못읽어 출력란에만 %15746을 해주었다;;; 

 

-정답 코드

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[] cnt;
    static int func(int n)
    {
        cnt[0] = 1;
        cnt[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            cnt[i] = (cnt[i - 1] + cnt[i - 2])%15746;
        }
        return cnt[n];
    }
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        cnt = new int[1000001];
        int n = int.Parse(sr.ReadLine());
        func(n);
        sw.WriteLine(cnt[n]);
        sr.Close();
        sw.Close(); 
    } 
}