백준 4902 : 삼각형의 값

https://www.acmicpc.net/problem/4902

4902번: 삼각형의 값

 

누적합 문제 같은데 누적합을 어떻게 구해야하나 고민이 많이 됐던 문제다.

결론부터 말하자면 층 별로 누적합을 구해두고 삼각형의 값을 구할 때 층별로 값을 더해나가면 된다.

 

층 별로 누적합을 구해야한다는 아이디어가 떠오르지 않아 오늘도 jinhan814님의 풀이를 참고했다.

https://blog.naver.com/jinhan814/222224999301

[BOJ] 4902번 - 삼각형의 값

 

#include <iostream>

#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std;

int n;
int tri[401][800];
int prefix[401][800];

int find_max_val() {
	int cur, max_val = -1e9;

	//정방향 삼각형
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < 2 * i; j += 2) {
			cur = 0;
			for (int k = 0; k <= n - i; k++) {
				cur += prefix[i + k][j + 2 * k] - prefix[i + k][j - 1];
				max_val = max(max_val, cur);
			}
		}
	}

	//역방향 삼각형
	for (int i = n; i >= 1; i--) {
		for (int j = 2; j < 2 * i; j += 2) {
			cur = 0;
			for (int k = 0; k <= n; k++) {
				if (j - 2 * k - 1 < 0 || j >= 2 * (i-k)) break;
				cur += prefix[i - k][j] - prefix[i - k][j - 2 * k - 1];
				max_val = max(max_val, cur);
			}
		}
	}

	return max_val;
}

void solution() {
	int max_val, tc = 0;
	while (1) {
		cin >> n;
		if (!n) break;

		++tc;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j < 2 * i; j++) {
				cin >> tri[i][j];
				//층 별로 누적합 구하기
				prefix[i][j] = tri[i][j] + prefix[i][j - 1];
			}
		}
			
		max_val = find_max_val();
		cout << tc << ". " << max_val << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 4528 kb

시간: 88 ms