[C++로 풀이] 2 X n 타일링 (dp)⭐⭐⭐

📌 2 X n 타일링

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    vector<int> arr(2);
    arr[0] = 1;
    arr[1] = 1;
    
    for(int i = 2; i <= n; ++i)
        arr.push_back((arr[i - 1] + arr[i - 2]) % 1000000007);
    answer = arr[n];
    
    return answer;
}

“피보나치 수열”을 Dynamic Programming 방식으로 풀었다.

우연찮게 규칙을 찾아보니 피보나치 수열이길래.. 피보나치 수열이 정답인가? 하고 실행해보니 진짜 맞았다..ㅋㅋㅋㅋ 일단 입력 크기가 워낙 크니 재귀로 풀면 안되고 DP 로 풀어야 한다는 것은 확실!

✈ 피보나치인 이유

• 가로 길이가 n이 되는 타일링 방법
  • n-1이 되는 타일링 방법에서 가로 길이 1 인 세로 타일 1 개 추가하기
  • n-2이 되는 타일링 방법에서 가로 길이 2 인 가로 타일 1 개 추가하기

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기