알고스팟 asymtiling 문제 파이썬으로 풀기

tiling 관련 문제가 다 그렇듯, 타일을 주어진 도형으로 채우는 문제이다. 타일은 겹쳐서는 안되고, 90도 회전은 가능하지만, 타일링이 좌우 대칭이어선 안된다.

대칭을 허용하지 않는다는 조건을 뺏으면 쉬운 문제였을 거 같지만, 대칭이 안되기 때문에 생각을 좀 했어야 했다.

이것저것 생각을 하다 마땅히 떠오르는게 없어서 풀이를 찾아보다가 이런걸 발견했다.

출처: https://blog.naver.com/hades2015/220418913713

즉 이 문제에서 구할 것은 타일을 놓을 수 있는 전체 경우의 수에서 대칭되는 경우의 수를 빼면 된다는 것이다.

더욱 구체적으로 말하면, 2*n크기의 직사각형을 채우는 비대칭 타일링 방법의 수는 

n번째 피보나치 수, 즉 타일링이 가능한 전체 수에서

n이 홀수일 때는 (n-1)/2 번째의 피보나치 수를 빼고,

n이 짝수일 때는 (n+2)/2 번째의 피보나치 수를 빼주면 되었다. (정확히 왜 이런지 이유는 잘 모르겠지만 값은 맞다)

쉽게 이해할 수 있었고, 코드로 짜기도 쉬워보여서 이 방식을 채택하여 코드를 짜 보았다.

피보나치 수를 저장하는 배열을 만들고, (저장을 안하면 매 횟수마다 피보나치 수를 계산하고 있을 거 같고, 즉 실행시간이 엄청 늘어나기 때문에 배열에 저장하는 식으로 시간을 줄이고 싶었다) n을 받아(내 코드에선 num) n번째까지의 피보나치 수를 만든다. 그 후 n이 짝수면 (n+2)/2를 해주고 n번째 피보나치 수에서 (n+2)/2번째 피보나치 수 (내 코드에선 nums번째 피보나치 수)를 빼준다. n이 홀수면 홀수대로 처리를 해준다.

n이 1이나 2일때는 숫자가 작아서 계산 과정을 안거치고 바로 result에 값을 넣어주었다.

문제에 나온 예시를 실행해 봤더니 잘 되었다

정답을 제출하니

맞았다.

 

느낀점:

1. 역시 타일링 문제는 피보나치 수와 연관이 되어있다. 왜 정확히 그런것인지 이유는 모르겠다.

2. 피보나치 수를 일일히 다 계산하면 실행시간이 엄청 길어지는데, 그걸 방지하기 위해 배열에 저장하는 건 개인적으로 괜찮은 방식인거같다. 다른 방식도 있을거 같긴한데...

3. 

출처: https://tibyte.kr/233

이렇게 더욱 수학적으로 파고든 풀이도 있었는데, 앞서 본 방법이 더 이해가 쉬웠다. 그렇다고 이 풀이가 틀린건 아닌거 같고, 난 그저 내가 쉽게 이해했던 것을 썻다.