[ 프로그래머스 ] 산 모양 타일링 (C++)

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

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : DP 
풀이 시간 : 28분 

문제 풀이 

문제를 읽어보면, 이후에 계산하는 결과가 이전 결과에 영향을 미치지 않는 구조로 되어있다. 또한, $N ≤ 100000$으로 꽤나 큰 범위를 갖고 있다. 따라서 다음 문제는 DP로 접근을 할 수 있다.

문제에서 생각해야 할 부분은 두 가지 경우가 존재한다. 

1. 위쪽에 삼각형이 있는 경우
2. 옆쪽 삼각형을 침범하는 경우

여기서 옆 삼각형을 침범하지 않는 경우는 위쪽 삼각형이 있을 때와 없을 때로 나뉘게 되는데, 위쪽에 삼각형이 있다면, 다음과 같은 점화식이 나온다. $t = nt * 3 + n_attack_t * 2$

또한, 위쪽에 삼각형이 없다면 다음 점화식이 나오게 된다. $t = 2 * nt + n_attack_t$

이후, 새로운 이동을 위해 위 경우를 계산해준 식에 $n_attack_t = attack_t, nt = t$위 점화식을 통해 업데이트를 진행해주면 된다.

 

코드

/*
세 가지 경우로 나누어서 dp 식 세우기
마지막은 무조건 1임
1. 위에 삼각형이 있는 경우 
    t = nt * 3 + n_attack_t * 2
2. 위에 삼각형이 없는 경우
    t = 2 * nt + n_attack_t
이후 새로운 점화식
    n_attack_t = attack_t, nt = t;
*/

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

int solution(int n, vector<int> tops) {
	int attack_t, t, n_attack_t, nt;
	n_attack_t = 0, nt = 1;
	for (int i = 0; i < tops.size(); i++)
	{
		attack_t = n_attack_t + nt;
		if (tops[i] == 1)
		{
			t = nt * 3 + n_attack_t * 2;
		}
		else
		{
			t = 2 * nt + n_attack_t;
		}
		n_attack_t = attack_t, nt = t;
		n_attack_t %= 10007, nt %= 10007;
	}
	return (t + attack_t) % 10007;
}

배운 점 

DP는 점화식을 세우는 과정까지가 매우 어려운 것 같다. 계속 생각하고 비슷한 유형의 문제를 많이 풀어보면서 직접 그려가는 과정을 많이 거쳐야 할 것 같다.