백준 10109(Troyangles)

www.acmicpc.net/problem/10109

10109번: Troyangles

 

Rebro님이 최근 코포와 동일한 문제가 있다고 해서 풀어보았다. 

 

 *

*** 이런식의 좌우 대칭이면서 i번째 높이에는 2i-1 갯수의 별이 존재하는 트리의 갯수의 합을 구하는 문제이다. 

 

트리의 꼭대기부터 트리가 몇개가 나오는지 세보면 대략 O(n^2 * n^2), O(n^4)의 시간복잡도가 필요하고, 이렇게 된다면 2000^4 당연히 시간초과가 나게 된다. 

 

근데 트리를 위 같은 과정으로 세다보면 알 수 있는게 중복된걸 계속해서 세고 있다는 점이다. 따라서 중복된 걸 세지 않도록 메모이제이션 즉 dp를 이용한다. 

 

dp[i][j] = 트리 꼭대기로 하는 가장 높은 트리 

 

dp[i][j] = min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) +1 

 

나머지는 인덱스 예외처리 잘 처리하면 된다.

#include<iostream>
#include<algorithm>
using namespace std;

char mat[2005][2005];
int dp[2005][2005];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mat[i][j];
		}
	}
	int ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			if (mat[i][j] == '.')continue;
			if (j + 1 > n - 1 || j - 1 < 0) {
				dp[i][j] = 1;
				ans++;
			}
			else {
				dp[i][j] = min({ dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j - 1] }) + 1;
				ans += dp[i][j];
			}
		}
	}
	cout << ans << '\n';
}