BOJ-1932-정수 삼각형

[changicho]

1932. 정수 삼각형

링크

난이도	정답률(_%)
Silver I	58.526

설계

메모이제이션

memo[i][j] = max(memo[i-1][j-1]+arr[i][j], memo[i-1][j-1]+arr[i][j])

일반항을 위와 같이 정할 수 있다.

index가 0미만이 되는 경우를 없애기 위해 배열의 0번째는 전부 빈칸으로 두고 1부터 시작한다.

정리

내 코드 (ms)	빠른 코드 (ms)
8

고생한 점

한동안 실행이 제대로 되지 않았다. 이유를 찾지 못함

코드

#include <algorithm>
#include <iostream>

using namespace std;

int map[502][502] = { 0, };
int memo[502][502] = { 0, };

void solution() {
	int N, sum = 0;

	cin >> N;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> map[i][j];

			memo[i][j] = max(map[i][j] + memo[i - 1][j - 1], map[i][j] + memo[i - 1][j]);
		}
	}

	int answer = 0;
	for (int i = 0; i <= N; i++) {
		answer = max(answer, memo[N][i]);
	}

	cout << answer << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}