[C언어] 백준 1932 : 정수 삼각형

생각의 흐름

저장하면서 가야겠구나 dp 해야되겠구나 배열 써서 거기에 저장 해야겠구나 이차원배열을 써야되겠구나 최대값을 구해야하니 max로 판별을 해야되겠구나 끗

내가 푼 코드

#include <stdio.h>

int dp[501][501];

int Max(int a, int b)
{
	return a > b ? a : b;
}

int main()
{
	int i, n, j;
	int max = -1;
	scanf("%d", &n);
	i = 1;
	while (i <= n)
	{
		j = 1;
		while (j <= i)
		{
			scanf("%d", &dp[i][j]);
			j++;
		}
		i++;
	}

	i = 1;
	while (i <= n)
	{
		j = 1;
		while (j <= i)
		{
			if (j == 1)
				dp[i][j] = dp[i][j] + dp[i - 1][j];
			else if (j == i)
			{
				dp[i][j] = dp[i][j] + dp[i - 1][j - 1];
			}
			else
			{
				dp[i][j] = dp[i][j] + Max(dp[i - 1][j - 1],dp[i - 1][j]);
			}
			if (max < dp[i][j])
				max = dp[i][j];
			j++;
		}
		i++;
	}
	printf("%d", max);
}

맨 왼쪽과 오른쪽을 구분해서 진행한다. 어차피 선택지가 한개이기 때문.
나머지는 최대값을 골라가며 저장한다. 마지막줄에 대충 10 11 15 13 12 이렇게 저장될텐데 돌아갈때마다 max를 기억하면서 하면 15가 저장되고 끝이난다.