문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 타일을 가로로 배치 하는 경우, 타일을 세로로 배치 하는 경우의 2가지 방법이 있습니다. 예를 들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 가로의 길이 n은 60,000이하의 자연수 입니다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
조건
1. 가로 길이가 2, 세로의 길이가 1인 직사각형모양의 타일 2. 타일로 세로의 길이가 2, 가로의 길이가 n인 바닥을 가득 채운다 3. 타일은 가로 배치, 세로 배치 모두 가능하다 4. 직사각형을 채우는 방법의 수를 1,000,000,007으로 나눈 나머지를 리턴 5. n은 60,000이하의 자연수
풀이 방법
1. 규칙 확인 : # a는 필요한 타일 개수 n=1, a=1 | n=2, a=2 || = n=3, a=3 ||| |= =| n=4, a=5 n=5, a=8 n=6, a=13 ... 피보나치 수열임을 그려서 확인함 2. 반복문으로 직전의 두 수만 계속 저장하면서 최종값 계산 -> while문 돌리기 3. n=1, a=1/n=2, a=2는 고정, 3부터 시작 4. 1,000,000,007으로 나눈 나머지를 리턴
작성 코드
def solution(n):
# 3
n_1=2 # 앞으로 n-1 저장
n_2=1 # 앞으로 n-2 저장
n=n-2
while (n>=1) : #2
result = n_1+n_2 #앞으로 n-1 + n-2의 결과 저장
n_2=n_1
n_1=result
n-=1
return result%1000000007 #4
결과
연습문제 카테고리의 난이도 Lv.2 문제
규칙이 있겠구나 싶어서 직접 그려서 피보나치 수열임을 확인하느라 시간이 좀 걸린 문제.
나는 이렇게 풀었지만 다른 풀이를 보니 for문 - 점화식을 사용하는 게 정석인 듯 싶었다.
