백준 1932

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

1932번: 정수 삼각형

이 문제의 경우 여러가지 생각을 하게 해주었다 일단 처음에 visual studio 에서 

스택 사이즈를 너무 많이 먹는다고 경고를 띄우고 강제 종료되서 나를 개빡치게 했다

이건 지역변수가 스택에 할당 되서 문제였다

그래서 문제 해결법은 그냥 전역변수에 사이즈가 큰 배열을 갔다 박으면 되는 문제였다

또한 short로 하면 이문제는 틀렸습니다가 나온다 그이유는 각각의 수의 범위들은 short로

처리가 가능하지만 이 값들의 합은 short 범위 내에 있지 않을 가능성이 크기 때문이다

이에 변수들을 int로 정의 해주면 해결이었다

dp에 bottom up방식을 사용해서 풀었다.

나는 이문제가 이전에 풀었던 2 3짜리 문제 보다 훨씬 쉬었다

이문제의 경우 총 3개의 경우의 수를 생각해주어야한다

삼각형의 왼쪽끝과 오른쪽끝 그리고 이둘다 아닐경우가 다다르다

왼쪽끝과 오른쪽끝의 경우 자신의 부모가 하나밖에 없기 때문에 확정으로 값이 나온다

왼쪽은 이렇게 dp[j][k] = tri[j][k]+ dp[j - 1][k];

오른쪽은 이렇게 dp[j][k] = tri[j][k] + dp[j - 1][k-1];

둘다 아닌경우는 dp[j][k] = max((tri[j][k] + dp[j - 1][k]), (tri[j][k] + dp[j - 1][k - 1]));

이렇게 3개로 나누어줘야한다 아니면 불필요한 범위까지 계산하게 되서 백준에서 오류를 띄워준다.

#include <iostream>
using namespace std;
int tri[501][501];
int dp[501][501];

int max(int x, int y) {
	return x > y ? x : y;
}
int main() {
	int trisize;
	cin >> trisize;
	int maxnum = 0;

	for (int i = 0; i < trisize; i++) {
		for (int j = 0; j < i + 1; j++) {
			cin >> tri[i][j];
		}
	}
	dp[0][0] = tri[0][0];
	for (int j = 1; j < trisize; j++) {
		for (int k = 0; k <= j; k++) {
			if (k == 0) {
				dp[j][k] = tri[j][k]+ dp[j - 1][k];
			}
			else if (k == j) {
				dp[j][k] = tri[j][k] + dp[j - 1][k-1];
			}
			else {
				dp[j][k] = max((tri[j][k] + dp[j - 1][k]), (tri[j][k] + dp[j - 1][k - 1]));
			}
		}

	}
	for (int i = 0; i < trisize; i++) {
		if (dp[trisize-1][i] > maxnum) {
			maxnum = dp[trisize - 1][i];
		}
	}
	cout << maxnum;
}