BOJ13301

12344 단어 DPDP

BOJ13301. 타일 장식물

문제

코드

시간초과..


#include <iostream>

using namespace std;

long long targetN(int x)
{

    if (x == 1)
        return 1;
    else if (x == 0)
        return 0;
    else
        return targetN(x - 1) + targetN(x - 2);
}

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    long long result = 0;
    long long garo = 1;
    long long sero = 1;
    for (int i = 1; i <= n; i++)
    {
        long long temp = targetN(i);

        if (i == 1)
        {
            result = ((temp) + (temp)) * 2;
        }
        else if (i % 2 == 0)
        {
            sero += temp;
            result = ((temp) + (sero)) * 2;
        }
        else if (i % 2 != 0)
        {
            garo += temp;
            result = ((garo) + (temp)) * 2;
        }
    }

    cout << result << '\n';

    return 0;
}

짝수의 숫자를 입력하면 세로길이가 증가하고,
홀수의 숫자를 입력하면 가로길이가 증가한다.

증가하는 길이는 바로 피보나치수의 누적 값만큼 늘어난다.

늘어난 길이의 가로,세로 총 합 * 2

시간초과 오류 발생...

참조


#include <iostream>

using namespace std;

long long dp1[81];
long long dp2[81];

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    dp1[1] = 1, dp1[2] = 1;
    for (int i = 3; i <= 80; i++)
    {
        dp1[i] = dp1[i - 1] + dp1[i - 2];
    }

    dp2[1] = 4;

    for (int i = 2; i <= 80; i++)
    {
        dp2[i] = dp2[i - 1] + dp1[i] * 2;
    }

    cout << dp2[n] << '\n';
    return 0;
}

현자타임.. 🤨

좋은 웹페이지 즐겨찾기