[programmers] 프로그래머스 Level3 2 x n 타일링(파이썬 Python)

(주)그렙

 

[programmers] 프로그래머스 Level3 2 x n 타일링

(파이썬 Python)

 

* 문제출처 : 프로그래머스 코딩 테스트 연습, 알고리즘 문제

 

 

 

1) 문제

---

 

코딩테스트 연습 - 2 x n 타일링

 

 

 

 

 

2) 코드

---

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

 

 

 

 

3) 풀이 과정

---

n = 4 / result = 5기점으로

 

n = 1,2,3까지 보기좋게 숫자 체계로 표현

(직접 그림으로 그려도 봐야 함.)

 

n = 1 - > result = 1

n = 2 - > result = 2

n = 3 - > result = 3

n = 4 - > result = 5

 

우선 나름 규칙을 파악 하여 가설을 세움

 

1과 2를 더하면 - > 3

2와 3을 더하면 - > 5

 

되네?.

근데 이건 확실치 않은 정보.

 

 

 

 

 

 

그리고 나서 그림으로 다시 확인

 

위 - > 아래 : n = 1 - > 3 으로 갈 때의 result값 그림

n = 4 일 때 result 값

 

 

결국, 아래의 점화식을 세울수가 있음.

 

2 x n 짜리로 만들 수 있는 경우의 수 =

 

(2 x n-1 로 만들 수 있는 경우의 수 + 세로 막대기 추가) + (2 x n-2 로 만들 수 있는 경우의 수 + 가로막대기 2개)

 

즉,

A n = A n-1 + A n-2

         (세로 1개) (가로 2개)

 

 

 

n = 1 일때 arr[0]

n = 2 일때 arr[1]

n = n 일때 arr[n-1]

 

이므로 return할시 arr[n-1]

 

 

 

 

 

 

 

4) 정리 노트

---

* Dp로 분류되어 있어서 Dp로 푸는 것이 아니라,

부분합으로 전체를 구해야 하니까 Dp로 푸는 것이다.

 

또한 숫자 체계로 먼저 접근하는 것 보다 일단 그림으로 그려서, 확인 작업하는게 중요하다.

숫자로만 파악하는 경우 정확성이 떨어짐.

 

* Dp는 점화식만 구하면 매우 쉽게 접근이 가능하며,

Top - >Down 방식과

Down - > Top 방식이 존재한다.