[프로그래머스] 2단계 - 2 x n 타일링

문제 설명

2 x 1 타일이 있을 때 2 x n 직사각형을 채우는 방법의 수를 return

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

프로그래머스

 

 

문제 풀이법

전형적인 dp 문제이다

 

2 x 4까지 그려보면 규칙을 발견할 수 있을텐데

2 x 1은 1개, 2 x 2는 2개 이고 2 x n은 n - 1 + n - 2이다

피보나치 수열과 동일하다

 

그리고 문제에서 1000000007 로 나눈 나머지를 return 하라고 했으므로 이 점을 주의해야한다

근데 이 문제에서 꽤나 시간초과가 발생하는데 왜..그런지는 아직 모르겠다

//시간 초과 난 코드
arr[i] = ((arr[i - 1] % 1000000007) + (arr[i - 2] % 1000000007)) % 1000000007;

//정답 코드
arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;

 

 

소스 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int arr[600001];
    
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
    }
    
    return arr[n];
}