[프로그래머스] 2 x n 타일링 -JAVA

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

프로그래머스

 

문제의 접근을 위해 골똘히 생각해 봐야 한다.

결국 자연수 n길이의 박스에 길이가 1 또는 2의 막대기를 사용하여 일렬로 나열할수 있는 경우의 수이다.

 

예를 들어 n이 5라면

11111

2111

221

3가지 방법으로 이루어져 있다.

 

그렇다면 2 와 1의 개수 조합을 알고 있다면 조합과 순열을 통해 경우의 수를 구할 수 있을 것이다.

 

어떤 변수가 몇 개가 필요할까?

1의 개수를 담을 int타입의 변수와 2의 개수를 담을 int 타입의 변수가 필요하다.

 

int oneNum = 0;

int twoNum = 0; 

 

그런데 2 또는 1이 배치되는 개수를 내가 어찌아는가? 내가 만들어야지..

우선 모든 막대기를 2로 만드는것이다.

그렇다면 초기값은

oneNum = n % 2;

twoNum = n / 2;

n길이의 박스안은 짝수라면 2로 가득 찻을 것이고, 홀수라면  2와 1 한개가 존재할 것이다.

 

그렇다면 게임은 끝났다.

(oneNum +twoNum)! / (twoNum! * oneNum!)

을 하면 2가지를 나열하는 경우의 수를 구할 수 있다. (  (전체 개수!) / ( 2의 개수!) * (전체 개수 - 2의 개수)! )

int numCase = 0;

2 또는 1가 존재하는 모든 경우의 수를 더해야 하기에

while 문을 사용해야 할 것이다.

twoNum이 -1되면 oneNum은 +2 되어야한다.

그렇게 twoNum이 0이 될때까지 반복하여

numCase += (oneNum +twoNum)! / (twoNum! * oneNum!);

처럼 더해주면 모든 경우의 수가 나올 것이다.

 

팩토리얼 메소드를 구현하는데 매개변수가 0일때를 고려해서 짜주면 될 것이다.

그리고 long에도 담을수 없는 크기의 수가 나오기 때문에 BigInteger 클래스를 사용해야 할 것이다.

 

모든 문제는 풀이에 정답이 없다.

하지만 규칙이 잘 보이지 않고 어떠한 공식을 모른다고 안풀고 넘어갈 것인가?

 

어떻게든 풀어내야한다.

다른 풀이를 검색해보니 피보나치수열이니 뭐니 써놨는데 와닿지도 않는다.

어떻게든 풀어내보자..