[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

 

 

	#include <string>
	#include <vector>
	#include <stack>
	#define CONDITION 1000000007
	using namespace std;
	int solution(int n) {
	int pibo[60001]={0};
	pibo[1]=1;
	pibo[2]=2;
	int answer = 0;
	for(int i=3; i<=n;i++)
	{
	pibo[i]=(pibo[i-1]+pibo[i-2])%CONDITION;
	}
	answer=pibo[n];
	return answer%CONDITION;
	}
	int main(){
	int n=4;
	return solution(n);
	}

view raw 2xn tile.cpp hosted with ❤ by GitHub