문제 후기
단순히 숫자의 조합으로 해결할 수 있어서 처음에는 같은 수가 있는 순열 식을 활용하려 했다.
문제를 예를 들면 [2,1(a),1(b)] [2,1(b),1(a)] 와 같은 것이다.
계산 하는 방식은 총 갯수 n, 중복하는 숫자의 갯수 m이면 n!/ m! 이다. 따라서 1,2의 갯수만큼 나누는 것으로 했다. 하지만 Factorial의 특성으로 인해서 특정 숫자를 넘어가면 시간초과가 발생했다.
다시 처음부터 경우의 수를 확인해본 결과 1,2,3,5,8,13... 순으로 피보나치수열인 것을 확인할 수 있었다.
문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 가로의 길이 n은 60,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예
nresult
| n | result |
| 4 | 5 |
입출력 예 설명
입출력 예 #1
다음과 같이 5가지 방법이 있다.
# 같은 수가 있을 때 순열 공식을 활용.
def solution(n):
answer = 1
count_one = n - 2
count_two = 1
while count_one > 1:
answer += math.factorial(count_one+count_two) // (math.factorial(count_one) * math.factorial(count_two))
count_one -= 2
count_two += 1
# print(answer)
# print(count_one, count_two)
if count_one == 1:
answer += math.factorial(count_one + count_two) // (math.factorial(count_one) * math.factorial(count_two))
else:
answer += 1
return answer % 1000000007# 피보나치 수열로 계산
def solution(n):
answer = 1
start1 = 1
start2 = 2
num = 2
while num < n:
answer = start1 + start2
start1 = start2
start2 = answer
num += 1
return answer % 1000000007