[프로그래머스][LV.2] 2 x n 타일링 | python3

 

문제 링크: 2 x n 타일링

 

문제 설명

문제 설명

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

타일을 가로로 배치 하는 경우타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

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




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

 

---

문제 풀이

def facto(n):
    if n==1:
        return 1
    answer=2
    for i in range(n-1):
        answer+=i
    
    return answer

def solution(n):
    answer=facto(n)
    return answer%1000000007

처음에 문제를 착각하고 이렇게 풀었다.....1,2,3,4,,, 이런식으로 증가폭이 증가하는줄.... 

전혀아니였음..

첨에는 테스트에서 맞고 제출하면 틀리길래 왜 틀린지 이해가 안돼서 gtp한테 물어봤다가...힌트를 얻고 풀었다.

타일의 길이가 n일때의 값은 타일의 길이가 n-1 일때의 경우의 수 + n-2일 때의 경우의 수이다. 
즉, f(n) = f(n-1) + f(n-2) 이 성립된다.
재귀함수에 꽂혀서 그런가 이것도 재귀함수로 풀어보려고 했는데 수가 너무 커져서 에러가 났다.
결과에 1000000007을 나눴는데도...아마 풀이과정에서 문제가 생겼거나 코드자체가 잘못된것일듯.
그 코드를 지우면 안됐는데 지워버렸다ㅜㅜ

그래서 결국 피티씨가 알려준 방법을 참고했다.
길이가 n+1인 리스트를 만들어서 for문을 이용하여 값을 계산하여 넣어주면 된다. 첨에 왜 값을 나눈 나머지 값을 구하라는 건지 몰랐는데 코드를 풀고 나니 이해가 됐다.  

 

내코드

def solution(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    DF=[0]*(n+1)
    DF[1],DF[2]=1,2
    for i in range(3,n+1):
        DF[i]=(DF[i-1]+DF[i-2])%1000000007
    answer=DF[n]
    return answer

 

 

---

다른사람풀이

def solution(n):
    a, b = 1, 1
    for i in range(1, n):
        a, b = b, (a + b) % 1000000007
    return b

대박...완전 직관적이고 간결하다.a에는 b를 넣으면서 n-1일대의 값을 구하고 b는 n의 값이고..결국 n 일때 (n-2)와 (n-1)일 때의 값을 구하면 되니 range(1,n)으로 하면 됨.