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

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스

---

문제 설명

한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다.

이때 사라디 꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다.

이렇게 만든 모양을 정삼각형 타일 혹은 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채울려고 합니다.
이때 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 구하시오.

---

아이디어

● 1차 - 완전탐색

위에 삼각형이 없는 칸이라면 3가지 경우가 가능하고, 이 때 오른쪽 삼각형을 사용한 경우 다음 칸은 해당 삼각형 사용권이없습니다.

빨간 삼각형 기준 파랑 1, 2, 3

위에 삼각형이 있는 칸일때도 사용 가능여부에 따라 가짓수가 나뉩니다.

해당 방식으로 완전탐색을 진행하면 답을 구할 수 있다 생각합니다.

→ 1~10번 케이스 solve, 이후 케이스 시간 초과 : 반복적인 계산이 많으니 동적프로그래밍을 써야할 것 같다.

● 2차 - 동적 프로그래밍

다시 처음으로 돌아가 기본 삼각형 3개(n = 1)을 채우는 방법은 3가지, 2개가 추가된 경우(n = 2)는 8가지입니다.

이때 n=1에서 n=2로 확장될 때 ▰, ▲로 끝나는 경우 는 5가지, 그렇지 않은 경우는 3가지 입니다.
▰, ▲로  끝나는 경우 는 ①, ②에서 2개씩, ③에서 1개가 발생하고, 그렇지 않은 경우는 이전에서 각각 1개씩 발생합니다.

이를 정리하면 위에 삼각형이 없는 사다리꼴에 경우

▰, ▲로  끝나는 경우 = 이전 ▰로 끝나거나 삼각형으로 끝나는 경우 * 2 + 그렇지 않은 경우
dp1[n] = dp1[n-1] * 2 +  dp2[n-2] 

▰, ▲로 끝나지 않는 경우 = ▰로 끝나거나 삼각형으로 끝나는 경우 + 그렇지 않은 경우
dp2[n] = dp1[n-1] + dp2[n-1]

 

위에 삼각형이 존재하면 위를 향하는 마름모의 경우의 수가 추가되어 돌아갑니다.

▰, ▲로  끝나는 경우 = 이전 ▰로 끝나거나 삼각형으로 끝나는 경우 * 3 + 그렇지 않은 경우 * 2
dp1[n] = dp1[n-1] * 3 + dp2[n-2] * 2

▰, ▲로 끝나지 않는 경우 = ▰로 끝나거나 삼각형으로 끝나는 경우 + 그렇지 않은 경우
dp2[n] = dp1[n-1] + dp2[n-1]

---

코드 1 (완전탐색)

#include <string>
#include <vector>

using namespace std;
int answer = 0;

//cond = 직전 우측 삼각형 사용 가능 여부
void BF(int n, vector<int> tops, int cur, int calc, bool cond)
{
    if(cur == n)
    {
        answer += calc;
        return;
    }

    if(cond)
    {
        if(tops[cur] > 0)
        {
            BF(n, tops, cur+1, calc * 3, true);
            BF(n, tops, cur+1, calc , false);
        }
        else
        {
            BF(n, tops, cur+1, calc * 2, true);
            BF(n, tops, cur+1, calc , false);
        }
    }
    else
    {
        if(tops[cur] > 0)
        {
            BF(n, tops, cur+1, calc * 2, true);
            BF(n, tops, cur+1, calc , false);
        }
        else
        {
            BF(n, tops, cur+1, calc, true);
            BF(n, tops, cur+1, calc, false);
        }
    }
}

int solution(int n, vector<int> tops) {
    BF(n, tops, 0, 1, true);
    return answer % 10007;
}

코드 2 (DP)

#include <string>
#include <vector>

using namespace std;

int dp1[200001];
int dp2[200001];

int solution(int n, vector<int> tops) {
    if (tops[0] == 0){
        dp1[0] = 1;
        dp2[0] = 2;
    } else {
        dp1[0] = 1;
        dp2[0] = 3;
    }

    for (int i = 1; i < tops.size(); ++i){
        if (tops[i] == 1){
            dp1[i] = (dp1[i - 1] + dp2[i - 1]) % 10007;
            dp2[i] = (dp1[i - 1] * 2 + dp2[i - 1] * 3) % 10007;
        } else {
            dp1[i] = (dp1[i - 1] + dp2[i - 1]) % 10007;
            dp2[i] = (dp1[i - 1] + dp2[i - 1] * 2) % 10007;
        }
    }

    return (dp1[tops.size() - 1] + dp2[tops.size() - 1]) % 10007;
}

---