[프로그래머스 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입니다.

---

입출력 예ntopsresult

4	[1, 1, 0, 1]	149
2	[0, 1]	11
10	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]	7704

---

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다. 문제에서 설명한 방법을 포함해 총 149가지 방법이 존재합니다.

따라서 149를 return 해야 합니다.

입출력 예 #2

문제 설명에 따라 만든 모양은 다음과 같습니다.

이 모양을 타일로 채우는 방법은 다음과 같이 총 11가지입니다.

따라서 11을 return 해야 합니다.

입출력 예 #3

경우의 수는 총 17,711가지입니다. 따라서 17711을 10007로 나눈 나머지인 7704를 return 해야 합니다.

---

풀이

Dynamic Programming을 사용해서 풀 수 있습니다.

기본적인 아이디어는 아래와 같습니다.

n번째 산까지 타일링할 수 있는 경우의 수 =  n-1번째 산까지 타일링할 수 있는 경우의 수 + n번째 산을 타일링할 수 있는 경우의 수.

 

위의 개념을 단순히 점화식으로 만들면 금방 풀릴 것 같습니다.

하지만, 인접한 두 개의 산이 하나의 타일을 공유한다는 점, 그리고 봉우리가 뾰족할 때와 아닐 때 경우의 수가 다르다는 점 때문에 생각해야 할 부분이 많습니다.

 

우선, 뾰족 산을 타일링 할 수 있는 경우의 수는 간단히 세볼 수 있습니다. 4가지 입니다.

뾰족하지 않은 산도 간단히 세볼 수 있습니다. 3가지 입니다.

즉, 뾰족하거나 뾰족하지 않거나에 의한 경우의 수의 차이는 1개입니다. 뾰족함 문제는 크게 고민할  필요 없을 것 같습니다.

 

더 큰 문제는, 공유되는 타일 문제입니다. 

n+1번째 산까지 타일링하는 경우의 수를 알기 위해서는 n번째 산까지의 경우의 수를 알아야 합니다.

n번째 산을 타일링 할 때, n+1번째 산과 공유되는 타일(n번째 산의 마지막 타일)에 마름모 모양 타일을 깔았는지 아닌지(즉, 공유되는 타일을 차지했는지)에 따라 경우의 수를 나눠봅시다. 

n번째 산을 깔 때 마지막 타일을 차지하는 경우의 수는 단 1개입니다. 

n번째 산을 깔 때 마지막 타일을 차지하지 않는 경우의 수는 2~3개(뾰족하면 3개 아니면 2개) 입니다.

각각의 경우에

n+1번째 산을 마지막 타일을 차지하지 않고 타일링 하는 경우와,

마지막 타일을 차지하고 타일링하는 경우를 또 나눌 수 있겠습니다.

 

그렇다면 n+1번째 산까지 타일링하는 경우의 수는 아래와 같습니다.

n+1번째 산까지 타일링하는 경우의 수

= n+1번째 산까지 마지막 타일을 차지하지 않고 타일링하는 경우의 수

   + n+1번째 산까지 마지막 타일을 차지하고 타일링하는 경우의 수

= n 번째 산까지 마지막 타일을 차지하지 않고 타일링하는 경우의 수 * n+1번째 산을 마지막 타일을 차지하지 않고 타일링하는 경우의 수

  + n 번째 산까지 마지막 타일을 차지하지 않고 타일링하는 경우의 수 * n+1번째 산을 마지막 타일을 차지하고 타일링하는 경우의 수

  +  n 번째 산까지 마지막 타일을 차지하고 타일링하는 경우의 수 * n+1번째 산을 마지막 타일을 차지하지 않고 타일링하는 경우의 수

  +  n 번째 산까지 마지막 타일을 차지하고 타일링하는 경우의 수 * n+1번째 산을 마지막 타일을 차지하고 타일링하는 경우의 수

 

위 식이 점화식입니다. 이 점화식을 가지고 DP를 사용해 풀 수 있습니다.

저의 경우 DP1과 DP2라는 동적 배열을 선언하고,

DP1에는 n번째 산까지 마지막 타일을 사용하지 않고 타일링하는 경우의 수를 저장,

DP2에는 n번째 산까지 마지막 타일을 사용하고 타일링하는 경우의 수를 저장했습니다.

 

추가로, 정답은 경우의 수를 10007로 나눈 나머지입니다.

그런데 그냥 최종 경우의 수를 구하고 10007로 나눈 나머지를 제출하면 오답이 되는 테스트 케이스들이 있습니다.

이는 자료형이 표현할 수 있는 숫자보다 월등히 많은 경우의 수가 발생해서 오버플로우가 발생한 결과로 보입니다.

이 문제의 해결법은 DP 배열에 들어갈 경우의 수를 계산할 때 마다 10007로 나눈 나머지를 넣어주는 것입니다.

10007을 넘어간 숫자는 아무리 곱하고 더해도 10007을 넘어가기에, 10007이하의 숫자에 영향을 주지 않습니다. 따라서 미리 나머지 연산을 해준다고 해도 아무런 문제가 없습니다.

 

---

코드

#include <string>
#include <vector>

using namespace std;

int* DP1;
int* DP2;
int solution(int n, vector<int> tops) {
    int answer = 0;
    //DP1[n] =  마지막 타일을 사용하지 않았을 때, n 번째 봉우리까지의 경우의 수
    //DP2[n] =  마지막 타일을 사용했을 때, n 번째 봉우리까지의 경우의 수
    DP1 = new int[n];
    DP2 = new int[n];
    
    DP1[0] = tops[0] + 2;
    DP2[0] = 1;
    
    for(int i = 0 ; i < n-1 ; i ++)
    {
        DP1[i+1] =( DP1[i]* (2+tops[i+1]) + DP2[i] *(1+tops[i+1]))%10007;
        DP2[i+1] =( DP1[i] + DP2[i])%10007;
    }
    return (DP2[n-1] + DP1[n-1]) % 10007;
}