[2024 KAKAO WINTER INTERNSHIP] 산 모양 타일링 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/258705?language=cpp

프로그래머스

풀이

DP를 활용하여 문제를 풀어야겠다는 것은 쉽게 알 수 있지만, 어떻게 활용해야 하는지 고민하게 만드는 문제이다.

 

먼저 맨 왼쪽 아래 삼각형을 기본으로 삼고, 높이가 1일 때와 0일 때를 구분하면 [1, 1, 0, 1]을 위와 같이 표현할 수 있다.

 

이어서 높이가 1인 타일을 추가할 때 경우의 수에 대해서 생각해보자.

먼저 높이가 1인 타일을 칠하는 방법은 위 그림의 1, 2, 3번 3가지이다.

따라서 (이전 타일을 칠하는 경우의 수) * 3을 하면 모든 경우의 수를 구한 것 같지만, 그렇지 않다.

 

1번과 같이 노란색으로 칠한 부분이 삼각형일 때 이를 접하는 삼각형과 합쳐 마름모로 칠할 수 있기 때문이다.

 

높이가 0인 타일 역시 마찬가지이다.

타일을 칠하는 경우의 수는 2가지이지만, 접하는 부분의 삼각형을 합쳐 마름모로 만들 수 있음에 유의해야 한다.

그런데 위와 같이 오른쪽 접하는 부분이 삼각형이 아닌 마름모라면 어떨까?

접하는 부분을 마름모로 만들 수 없기 때문에, 이 경우는 1가지이다.

 

따라서, DP를 "오른쪽이 삼각형으로 칠해지는 경우"와 "오른쪽이 마름모로 칠해지는 경우" 두 가지로 나누어 저장할 것이다.

 

위 표의 행은 맨 오른쪽 타일이 삼각형 또는 마름모로 칠해질 때 경우의 수, 열은 n이다.

기본값은 삼각형 하나이기 때문에 dp[0][0]= 1, dp[0][1]=0이다.

 

다음으로 n=1일 때를 살펴보자. top의 값이 1이므로 칠할 수 있는 경우의 수는 위와 같다.

그리고 위 3가지 중 맨 오른쪽 타일이 삼각형인 것은 (1, 2) 2개, 마름모인 것은 (3) 1개이다.

 

dp[1][0]은 맨 오른쪽 타일이 삼각형인 경우이므로, 2가지 경우의 수가 있다.

따라서 (이전 타일을 칠하는 경우의 수) * 2 를 하되, 접하는 지역이 삼각형인 경우를 고려하여

(맨 오른쪽이 삼각형인 이전 타일을 칠하는 경우의 수)를 추가로 더해주어야 한다.

 

dp[1][1]은 맨 오른쪽 타일이 마름모인 경우이므로, 1가지 경우의 수가 있다.

따라서 이전 타일을 칠하는 경우의 수가 곧 dp[1][1]이다.

 

이와 같은 방식으로 모든 타일을 채워나가면 위와 같다.

최종 정답은 dp[4][0] + dp[4][1] = 149이다.

 

코드

#include <string>
#include <vector>
#define MOD 10007

using namespace std;


int dp[100001][2];

int solution(int n, vector<int> tops) {
    int answer = 0;
    
    // base case
    dp[0][0] = 1;
    dp[0][1] = 0;
    
    for (int i = 1; i <= n; i++){
        int cases = 1;
        if (tops[i-1] == 1){
            cases = 2;
        }
        
        int triangle = dp[i-1][0];
        int diamond = dp[i-1][1];

        dp[i][0] = ((triangle + diamond) * cases + triangle) % MOD;
        dp[i][1] = (triangle + diamond) % MOD;        
    }
    
    answer = (dp[n][0] + dp[n][1]) % MOD;
    
    return answer;
}