[C++ / Java] 프로그래머스 Level 2 - 2 x n 타일링

문제 링크 ↓ ↓ ↓ https://school.programmers.co.kr/learn/courses/30/lessons/12900 세로 길이가 2이고, 가로길이가 n으로 주어진다. 타일은 2가지 방식 중 하나로만 배치할 수 있다. 1. (1x2) 타일을 가로로 배치하는 경우 2. (2x1) 타일을 세로로 배치하는 경우 가로길이가 n일 때 나올 수 있는 경우의 수를 1,000,000,007로 나눈 나머지를 구하는 문제 문제 핵심 및 풀이 일단 답을 구할 때 1,000,000,007로 나누라고 한 거 보니 경우의 수가 엄청나게 많이 나올 것이라는 것을 예측할 수 있다.

가로( n)가 1일 때부터 나올 수 있는 패턴을 나열해 보자. 1,2,3,5 순으로 개수가 많아진다. 답을 구할 때 1,000,000,.....