프로그래머스 - 타일장식물 43104번

문제 :  https://programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 

풀이방식 

 

문제를 보고 규칙을 찾아보면 적힌 수가 1,1,2,3,5,8,13,21 ... 이렇게 진행을 한다.

 

즉, 피보나치 수열의 값을 가지는 것 을 확인 할 수 있다.

 

여기서 타일장식물의 한변의 길이를 살펴보면 처음에 1 1 일때는 가로 1 높이 2 값을 가지는 것을 확인 할 수 있다.

거기서 한변의 길이가 2인 정사각형 타일이 들어오게 되면 가로는 1+2 높이는 들어온 타일의 높이인 2인 것을 확인 할 수 있다. 그 다음에 3이 들어왔다고 가정을 해보자. 그러면 그러면 세로의 길이는 3+2 가로의 길이는 3인것을 확인 할 수 있다. 한가지의 경우만 더 해보자. 이 시점에서 한 변이 5인 정사각형 타일이 들어오게 되면 가로의 길이는 5+3 세로의 길이는 5 인 것을 확인 할 수 있다.

 

여기서 우리는 규칙을 찾을 수 있다.

 

세로의 길이 또는 가로의 길이 둘중 하나 중에 꼭 새로 들어온 타일의 변 길이 하나랑 같다는 규칙이 있다. 그러면 나머지 한변의 길이는 전에 있던 것 중에 가장 큰 변의 길이 중 가장 긴 애의 길이에다가 새로 들어온 타일의 한 변의 길이를 더해주면 된다.

 

그러므로 (새로들어온 변의 길이 * 2 + 이전에 있던 가장 긴 애의 한 변의 길이) 의 값은 가로+세로의 값을 의미하게 된다. 우리가 구하려고 하는 값은 둘레니깐 위의 값에다가 * 2 를 해주면 즉, (새로들어온 변의 길이 * 2 + 이전에 있던 가장 긴 애의 한 변의 길이) *2 를 해주면 답이된다.

 

추가로 자료형은 int형을 주게되면 오버플로우가 발생하기 때문에 long long 형으로 지정을 해주었다.

 

코드

#include <iostream>
#include <vector>

using namespace std;
long long result[100], answer;
int n, k;

long long fibo(int n)
{
    result[0] = 1;
    result[1] = 1;
    if (result[n] > 0)
        return result[n];
    if ((n == 0) || (n == 1))
        return result[n];
    return result[n] = fibo(n - 1) + fibo(n - 2);
}
long long solution(int N)
{
    fibo(N);
    if (N == 1)
    {
        return 4;
    }
    else if (N == 2)
    {
        return 6;
    }
    else
    {
        answer = (2 * result[N - 1] + result[N - 2]) * 2;
        return answer;
    }
}

int main()
{
    long long text = solution(70);
    cout << text;
}