[프로그래머스] 2 x n 타일링(C++)

https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

처음엔 재귀로 시도했던 문제.

함수 호출 시마다 가로로 두 개씩 눕혀 쓰는 fun(n-2), 세로로 하나 쓰는 fun(n-1)를 계속 호출했다.

그렇게 하니 작은 수를 다루는 테케는 통과했지만, 큰 수에서는 시간 초과가 났다.

 

다시 규칙을 찾아보니 피보나치인 것을 발견하여, 변수 a,b,c를 갖고 풀었다.

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int a=1;
    int b=2;
    if(n==1)
        answer=a;
    else if(n==2)
        answer=b;
    
    else
    {
        int c=0;
        for(int i=3;i<=n;i++)
        {
            c=(a+b)%1000000007;
            a=b;
            b=c;
        }
        answer=c;
    }
    return answer;
}