[Programmers Level2] 2xn타일링(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

프로그래머스

 

 

[문제 설명]

 

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

 

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

[제한 사항]

 

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

 

[입출력 예]

 

 

n	result
4	5

 

 

[입출력 예 설명]

 

입출력 예 #1

다음과 같이 5가지 방법이 있다.

 

 

[문제 풀이]

 

 

백준 11726번과 동일한 문제이지만 문제에서 주어진 가로 길이 범위가 다르다.

백준은 가로 길이 숫자 범위가 1 ~ 1000 이라면 프로그래머스는 1 ~ 60000까지였다.

백준 [11726번] 2xn 타일링(C++)

 

이미 백준에서 풀어보았지만 처음 풀어보는 것 처럼 노트에 그림을 그려가며 점화식을 구했다.

(피보나치 수열 점화식)

점화식 : dp[n] = dp[n-1] + dp[n-2]

 

그리고 각 연산 중간마다 모듈러 연산을 진행하여 오버플로우를 방지하고, Top - Down 방식으로 풀었다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;
#define MODULAR 1000000007

int dp[60001] = {0,};

int solution(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;

    if(dp[n] != 0) return dp[n] % MODULAR;
    else {
        dp[n] = (solution(n-1) + solution(n-2)) % MODULAR;
    }
    
    return dp[n];
}