[프로그래머스] 산 모양 타일링 (c++) DP 경우에 따라 여러개 사용하기

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스

 

풀이 방법

처음에는 완전 탐색을 이용해서 풀이했지만, 시간 초과가 발생했다.

문제를 살펴보면, 특정 상황이 반복되는 것을 확인할 수 있다.

하지만 다른 문제와 다르게 2가지의 상황이 반복되므로, DP를 두 개를 사용해야 했다.

또한 DP의 기준점을 정하는 것도 중요하다.

기준점으로 top으로 설정했다. (n개 이기도하고, 가장 명확한 기준점이 될 거 같아서)

또한 케이스를 나누어야 한다.

 

 

n = 2일 때, dp[1]을 구하려면 두 가지 경우로 나눌 수 있다: (왼쪽 세모가 0 오른쪽 세모가 1이다.)

(편의를 위해 자신의 세모에서 왼쪽 가장 아래를 침범 당할 수 있는 도형, 오른쪽 아래가 자신이 침범하는 것이라고 설정했다.)

1. 빨간 마름모가 있어 다음 세모 칸에 침범하는 경우

2. 빨간 마름모가 없어 다음 세모 칸에 침범하지 않는 경우

 

이를 위해 a[i]는 다음 세모에 침범하지 않는 경우, b[i]는 다음 세모에 빨간 마름모를 통해 침범하는 경우로 설정했다.

 

또한, 현재 위치에 top이 있는 경우와 없는 경우로 나눠 점화식을 설정했다.

• b[i]의 경우

b[i]는 i+1에서 침범이 확정된 상태이므로, top 유무에 관계없이고 자신의 침범이 되었는지 안되었는지 상관없이 모두 한 가지 경우만 가능하다. 그러므로  a[i-1] + b[i-1]로 계산한다.

• a[i]의 경우

top이 존재하고 i+1 칸에 침범하지 않으려면 세 가지 경우가 있습니다. 따라서 a[i-1] * 3이 되고, b[i-1]에서 침범이 일어난 경우는 두 가지 경우가 있으므로 b[i-1] * 2를 더해준다.

따라서,

 

a[i] = a[i-1] * 3 + b[i-1] * 2

 

• top이 없는 경우

a[i]는 a[i-1]에서 두 가지(마름모, 세모 두 개) 경우가 존재, b[i-1]에서 한 가지 경우가 있으므로

 

a[i] = a[i-1] * 2 + b[i-1]

이렇게 점화 식을 설정할 수 있다.

#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<int> tops) {

    int a[n+1], b[n+1];
    if (tops[0] == 0) { // 시작 점의 탑이 없을 때
        a[0] = 2, b[0] = 1; 
    }
    if (tops[0] == 1) { // 시작 점의 탑이 있을 때
        a[0] = 3, b[0] = 1;
    }
    
    for (int i=1; i < tops.size(); i++) { 
        if (tops[i] == 1) { // 현재 탑이 있는 경우
            a[i] = a[i-1] * 3 + 2 * b[i-1];            
        }
        else { // 현재 탑이 없는 경우
            a[i] = a[i-1] * 2 + b[i-1];

        }
        b[i] = b[i-1] + a[i-1]; // b[i]는 top이 있던 없던 경우가 같다.
        a[i] %= 10007, b[i] %= 10007;
    }    
    return (a[tops.size() - 1] + b[tops.size() - 1]) % 10007;
}