[C++][알고리즘] 프로그래머스:: 2 x n 타일링

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

프로그래머스

문제해설

규칙성을 찾는게 중요한 문제같습니다.

타일의 세로길이는 신경쓸 필요없으니 가로길이만 따진다 봤을 때

길이가 4인 타일 종류의 경우

1 1 1 1

1 2 1

1 1 2

2 1 1

2 2

이렇게 5가지인데,

배열로 생각하면

tile[맞춰야 하는 길이 n] = (경우의수)

tile[1] = 1

tile[2] = 2

tile[3] = 3

tile[4] = 5

tile[5] = 8 ...

이런식으로 피보나치수열의 형태가 됩니다.

따라서 피보나치 수열을 재귀적으로 풀이하면 되는데,

문제는 n의 범위가 6만까지이기 때문에 재귀함수형태로 풀면 아마 시간초과가 날겁니다.

 

그래서 저의 경우에는 stack 을 활용하였습니다. 결과값도 억이 가뿐히 넘기때문에

mod 연산 성질을 활용했습니다.

tile[n] mod n = (tile[n-1] mod n + tile[n-2] mod n) mod n과 같습니다

 

CODE