산 모양 타일링 [Lv.3]

코딩테스트 연습 - 산 모양 타일링 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

위를 바라보는 N + 1개의 삼각형, 아래를 바라보는 N개의 삼각형이 있으며 

tops 배열로 위에 붙여지는 추가 삼각형을 받습니다.

타일의 모양이 다양하여 어렵게 느껴질 수 있지만 평범한 타일 문제입니다.

 

풀이 방법

우선 이런 문제는 시간이 걸리더라도 실제 경우의 수를 계산해 볼 필요가 있습니다.

경우의 수를 그려놓고 패턴을 찾아보는게 중요합니다.

 

배열 tops안의 값들이 모두 0일 때의 경우의 수

N[0] = 1; (N이 0일 때)
N[1] = 3; (N이 1일 때)
N[2] = 8; 
N[3] = 21;

 

점화식을 구해보자면 아래와 같습니다.

N[i] = N[i-1] * 3 - N[i-2];

 

배열 tops안의 값들이 모두 1일 때의 경우의 수

N[0] = 1; (N이 0일 때)
N[1] = 4; (N이 1일 때)
N[2] = 15; 
N[3] = 56;

 

점화식을 구해보자면 아래와 같습니다.

N[i] = N[i-1] * 4 - N[i-2];

 

tops배열을 순회하면서 0이면 첫번째 점화식으로 1이라면 두번째 점화식으로 구하면 될것 같습니다.

// 0 =                    1
// 1 =            3               4 
// 2 =       8       11       11        15
// 3 =    21   29  30   41  29  40    41  56

왼쪽 자식 -> top이 0일 때, 오른쪽 자식 -> top이 1일 때

 

 

정답 코드

int solution(int n, vector<int> tops) {
    vector<int> v(n + 1);
    v[0] = 1;
    v[1] = 3 + tops[0];
    
    for (int i = 2; i <= n; i++) {
        v[i] = (v[i-1] * (3 + tops[i-1]) - v[i-2]) % 10007;
        
        if (v[i] < 0) 
        	v[i] += 10007;  // 음수를 방지
    }

    return v[n];
}