2xn 타일링

 

이번 문제는 프로그래머스의 연습문제 중 기하학 도형응 응용한 Case입니다.

 

programmers.co.kr/learn/courses/30/lessons/12900

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

 

문제를 살펴보면, 가로:세로 = 1:2의 종횡비를 갖는 직각 사각형을 가지고

 

2Xn형태의 타일을 채우는 문제입니다.

 

위 경우를 살펴보면, 

 

n이 1일 경우 1개

n이 2일 경우 2개

n이 3일경우 n=1인 경우와 n=2인 경우를 더한 값이 가능한 Case가 됩니다.

==> 이때 생각을 해보면, N-2까지를 채우고 나머지를 수평 직사각형 2개로 채우는 경우의수와

       N-1까지 채우고 나머지 1을 채우는 경우의 수를 더하면 N의 길이를 채우는 경우의수가 됩니다.

이전의 답이 다음 정답과 영향을 주는 Case로, 피보니치 수열과 정확히 일치하는것을 알 수 있습니다.

 

피보나치 수열을 이용한 풀이법입니다

def solution(n):    
    temp_list = []    
    temp_list.append(1)
    temp_list.append(2)
    for i in range(2, n):
        temp = temp_list[0]
        temp_list[0] = temp_list[1]
        temp_list[1] = temp + temp_list[0]        
    return temp_list[1]%1000000007

 

다른 풀이법으로는, Tree구조로 형상화하여 가능한 경우의수를 모두 찾는 방법입니다.

 

아래를 보시죠.

 

Tree구조를 사용해서 재귀적으로 해를 구하는 방법입니다.

Tree구조를 이용하는 방법

위 경우를 사려보면, 길이 N에 대해서 현재 N의 값을 통해서 가능한 경우의수를 모두 탐색합니다.

 

마지막 탐색 후 모든 Tree의 성장이 끝나고, Leaf Node의 수를 Count하면

 

가능한 모든 경우의수를 확인하는 것이 가능합니다 :)

 

하지만, 해당 방법은 이번 문제에서는 효율적인 답이 되지 못하네요. Runtime Error가 납니다.

 

Tree구조를 이용한 Case입니다 :)

class node:
    def __init__(self, left, current_length, sort, right):
        #left = horizental
        self.left = left
        self.len = current_length
        self.sort = sort
        #right = vertical
        self.right = right
        

class tree:
    def __init__(self, n):        
        #self.top_node = node(node(None, None, None, None), n, "top", node(None, None, None, None))
        self.top_node = node(None, n, "top", None)
        
    def case_gen(self, start_node = 999):
        result = 0
        if start_node == 999:
            start_node = self.top_node
        #if node_len > 1, then can add verti and hori
        if start_node.len >1:
            start_node.left = node(None, start_node.len-2, "hori", None)
            start_node.right = node(None, start_node.len-1, "verti", None)
        #if node_len == 1, only verti can be made
        elif start_node.len == 1:
            start_node.right = node(None, start_node.len-1, "verti", None)
        if start_node.left == None and start_node.right == None:
            return 1        
        #print(start_node.left, start_node.len, start_node.sort, start_node.right)
        if start_node.left !=None:
            result = result + self.case_gen(start_node.left)
        if start_node.right != None:
            result = result + self.case_gen(start_node.right)
        return result   
            


def solution(n):
    test = tree(n)
    answer = test.case_gen()    
    return answer%100000007

solution(2)