[Programmers Lv2, Java] 3 x n 타일링

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

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

 

프로그래머스

---

처음 문제를 봤을때는 못풀어서 푸는 방법에 대해서 봤는데 영어라서 대충 이미지만 기억해뒀다가 오늘 다시시도해서 풀었다.

 

내가 처음 문제에 접근할 때의 방식은가로 길이가 짝수가 아닌 경우는 성립하지 않으므로,

(3x홀수 = 홀수, 2칸 직사각형으로 모두 채울 수 없음)

가로길이 2씩 한 그룹으로 만들어서 모든 경우의수를 검사하는 방법을 사용했다.

'n=2) 직사각형이 떨어져 있는 경우는 각각 3개씩 경우의 수가 있으니, 3개'

'n=4) n=2가 2개있고, n=4가 1개'

'n=6) n=2가 3개 있고, n=4가 2개, n=6이 1개.'

이런 방식이었는데 자꾸 한 4개 5개씩 오버되는 오차가 발생해서 때려쳤었다.

 

실제로 오늘 문제를 푼 방식도 크게 다른 방식은 아니지만

길이가 홀수인 경우도 함께 계산하면 편했다는 사실을 알게됬다.

아래 링크는 문제 이해가 어려울 경우 참고하면 좋은 사이트 주소이다.

https://www.geeksforgeeks.org/tiling-with-dominoes/

Tiling with Dominoes - GeeksforGeeks

 

문제를 풀면서도 생각을 정리하기 위해 주석으로 남겨가면서 풀었다.

 

글을쓰고나서 다시 위 사이트에 들어가서 보니 코드가 많이 똑같은데..

뭐... 원리를 저기서 보고 생각한 결론이 나온거나 똑같을 수 밖에 없겠다는 생각이 들지만

먼가 좀 베낀 느낌이 들어서 찝찝하다