프로그래머스 산 모양 타일링 [Lv.3 정답률 23%] (C++)

프로그래머스

아랫변의 길이가 N+1인 사다리꼴이 있을 때 윗변과 변을 공유하는 n 개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙일 때, 아래 타일들로 빈 곳이 없도록 채울 수 있는 경우의 수를 구해주세요

 

풀이 방법

tops 배열이 모두 0일 때의 경우의 수를 먼저 구해 보겠습니다.

N이 0일 때의 경우의 수는 1,

N이 1일 때의 경우의 수는 3,

N이 2일 때의 경우의 수는 8

N이 3일 때의 경우의 수는 21 입니다.

즉 점화식을 만들어 본다면 아래와 같겠습니다.

dp[i] = dp[i-1] * 3 - dp[i-2] % 10007;

 

이 때, 주의할 점은 - dp[i - 2]를 하는 부분에서 dp[i]가 음수가 될 수도 있다는 것 입니다.

따라서 아래 코드를 꼭 추가해야 합니다.

if (dp[i] < 0)
    dp[i] += 10007;

 

이제 top 배열까지 고려해서 경우의 수를 생각해 보겠습니다.

N이 1이고 top 배열이 [0] 이라면 경우의 수는 3입니다.

N이 1이고 top 배열이 [1] 이라면 경우의 수는 4입니다.

N이 2이고 top 배열이 [0, 1]이라면 경우의 수는 11입니다.

N이 2이고 top 배열이 [1, 1]이라면 경우의 수는 15입니다.

즉, top배열의 해당 index에 1이 들어 있다면 점화식에서 3을, 4로 수정만 해주면 경우의 수를 구할 수 있게 됩니다.

따라서, 점화식을 아래처럼 수정해 준다면 되겠습니다.

dp[i] = (dp[i-1] * (3+tops[i-1]) - dp[i-2]) % 10007;

 

 

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n, vector<int> tops) {
    int answer = 0;
    vector<int> dp(n+1);
    dp[0] = 1;
    dp[1] = 3 + tops[0];
    
   
    for (int i = 2; i <= n; i++)
    {
        dp[i] = (dp[i-1] * (3+tops[i-1]) - dp[i-2]) % 10007;
        if (dp[i] < 0)
            dp[i] += 10007;
        cout << i << " : " << dp[i] << "\n";
    }
    return dp[n];
}