[Programmers] 산 모양 타일링 [C++]

문제 설명

문제 설명

한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다.

이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 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

문제 해석

1. i 번째 아래방향 타일을 덮는 경우의 수는 총 4가지 이다
   1. 위쪽 정삼각형과 함께 덮기
   2. 왼쪽 정삼각형과 함께 덮기
   3. 오른쪽 정삼각형과 함께 덮기
   4. 정삼각형 으로만 덮기
2. 3번째 방법을 i - 1 번째에 사용 했는가 안했는가로 나눌 수 있다
   1. a 배열 = i - 1 번째에 3번 방법을 쓴 경우의 수
   2. b 배열 = i - 1 번째에 3번 방법을 쓰지 않은 경우의 수
3. tops[i] = 1 일때
   1. a[i] = a[i-1] + b[i-1]
   2. b[i] = a[i-1] * 2 + b[i-1] * 3
4. tops[i] = 0 일때
   1. a[i] = a[i-1] + b[i-1]
   2. b[i] = a[i-1] + b[i-1] * 2

코드

#include <bits/stdc++.h>
using namespace std;

int solution(int n, vector<int> tops) {
    int answer = 0;

    /*
     * 각 아래방향 타일을 덮는 방법 4가지
     * 1. 위쪽 정삼각형과 함께 덮기
     * 2. 왼쪽 정삼각형과 함께 덮기
     * 3. 오른쪽 정삼각형과 함께 덮기
     * 4. 정삼각형으로 덮기
     *
     * 두개의 배열 필요
     * a 배열 = 3번 방법을 쓴 경우의 수
     * b 배열 = 3번 방법을 쓰지 않은 경우의 수
     */

    vector<int> a(100001,0), b(100001,0);
    a[0] = (0);
    b[0] = (1);

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

    answer = (a[n-1] + b[n-1]) % 10007;

    return answer;
}