알고스팟 타일링 TILING2 미완

 

https://algospot.com/judge/problem/read/TILING2

algospot.com :: TILING2

 

 

 

 

<접근방법>

이 문제를 처음 풀 때는 접근을 어떻게 할 지 몰라 막막했다.

그럴 때는 순서대로 예제를 만들어나가면서 규칙을 발견하는 것이 하나의 방법이다.

 

 

 

 

그림을 보면 하나의 규칙이 나온다는 것을 알 수 있다.

이것을 점화식으로 나타내보자.

점화식

 

 

기저사례에 유의하여 구현한다.

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

int tc, n;
int a[101][101], cache[101][101];


//좌표를 받아서 최대 경로의 갯수를 출력
int find(int y, int x) {
	if (y == n - 1) return 0;

	int &res = cache[y][x];
	if (res != -1) {
		cache[y][x]++;
		return res;
	}

	int now_val = a[y][x];

	res = max(find(y+1, x+1) + now_val, find(y+1, x) + now_val);

	return cache[y][x];
}

int main() {
	cin >> tc;
	while (tc--) {
		memset(cache, -1, sizeof(cache));

		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				cin >> a[i][j];
			}
		}
		cout << find(0, 0) << '\n';
	}

	return 0;
}

 

 

---

 

 

<느낀 점>

점화식의 규칙이 나오는 이유는 모르겠다..

전의 것이랑 합쳐서 사각형을 만들고 사각형 내부에서 위치 바꾸면서 모양 다르게 한다?

 

 

 

 

 

 

[참고]

-프로그래밍 대회에서 배우는 알고리즘 문제해결전략1