[99클럽/파이썬 챌린저/22일차] 산 모양 타일링

프로그래머스 산 모양 타일링 LV3

 

문제 설명
한 변의 길이가 1인 정삼각형 2n+1개를 이어 붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다. 예를 들어 n이 4이고, 1번째, 2번째, 4번째 정삼각형 위에 정삼각형을 붙인 모양은 다음과 같습니다. 이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다. 정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다. 타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다. 사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다. 이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.

제한사항
1 ≤ n ≤ 100,000
tops의 길이 = n
tops [i]는 사다리꼴의 윗변과 변을 공유하는 i+1번째 정삼각형의 위쪽에 정삼각형을 붙이는 경우 1, 붙이지 않는 경우 0입니다.
입출력 예

n	tops	result
4	[1,1,0,1]	149
2	[0,1]	11
10	[0,0,0,0,0,0,0,0,0,0]	7704

 

 

타일링은 dp 문제의 일종이다. 해당 문제는 2개의 딕셔너리를 사용하여 문제를 해결했다.

 

i-1번째와 i번째를 구분 짓기 위해 top의 유무와 관계없는 칸을 기준으로 잡아야 했다.

top이 생기는 위치의 우측 하단 정삼각형을 기준으로 잡았으며, 규칙을 찾기 위해 각 요소가 가능한 경우를 모두 확인했다.

 

한 칸이 빈 경우에 정 삼각형을 넣은 후 계산을 하면, 해당 경우는 가득 찬 경우와 다름이 없기 때문에, 중복 문제가 발생한다.

이를 방지하기 위해 마름모를 먼저 채워두고 가능한 경우를 따졌다.

 

 

해당 방법으로 가능한 모든 경우를 나열하였다.

 

해당 방식을 점화식으로 치환해보면

no_left [i] = one_left [i-1] + no_left [i-1] * (2 + top [i-1])

one_left [i] = one_left [i-1] + no_left [i-1] * (1 + top [i-1])

로 구할 수 있다.

 

가득 찬 경우만 반환해야 하므로, no_left [n]을 반환하였다.

 

 

def solution(n, tops):
    
    no_left = {0:1}
    one_left = {0:1}
    
    for i in range(1, n+1, 1):
        no_left[i] = (one_left[i-1] + no_left[i-1] * (2 + tops[i-1])) % 10007
        one_left[i] = (one_left[i-1] + no_left[i-1] * (1 + tops[i-1])) % 10007
        
    
    return no_left[n]

 

 

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> tops) {
    int answer = 0;
    
    int one_left = 1;
    int no_left = 1;
    
    int before_one, before_no;
    
    for(int i=1; i<=n; ++i)
    {
        before_one = one_left;
        before_no = no_left;
        
        no_left = (before_one + before_no * (2 + tops[i-1])) % 10007;
        one_left = (before_one + before_no * (1 + tops[i-1])) % 10007;
    }
    
    return no_left;
}

---

코드를 간소화한다면 가장 이전의 값만 저장하는 방식으로도 풀이할 수 있다.