[C] 백준 - 1932번: 정수 삼각형

3월 13일(월) - 동적계획법 1 (1932번)

1932번: 정수 삼각형

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 직전 RGB거리 문제와 동일한 형식으로 동적계획법을 이용한 풀이를 예상

- 2차원배열인 triangle에 정수 삼각형을 구성하는 정수들을 입력받음

- dp[1][1]에는 triangle [1][1] 값을, 다른 dp[i][j]값은 (dp[i-1][j-1] 과 dp[i-1][j] 중 더 큰 값) + triangle[i][j]로 설정

  하지만 삼각형 모양이기 때문에 각각의 한 줄에서 처음 시작하는 dp와 마지막 끝나는 dp는 따로 계산

- 이렇게 dp 값을 모두 채운뒤, 가장 마지막 n개의 dp중 가장 큰 값을 max 변수의 값으로 선언 및 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

x

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int MAX(int x, int y)
{
	return ((x > y) ? x : y);
}

int main(void)
{
	int triangle[501][501];
	int dp[501][501];

	int n;
	scanf("%d", &n);

	for (int i = 1; i < n + 1; i++)
	{
		for (int j = 1; j < i + 1; j++)
		{
			scanf("%d", &triangle[i][j]);
		}
	}

	dp[1][1] = triangle[1][1];
	for (int i = 2; i < n + 1; i++)
	{
		for (int j = 1; j < i + 1; j++)
		{
			if (j==1)
			{
				dp[i][j] = triangle[i][j] + dp[i - 1][j];
			}
			else if (j==i)
			{
				dp[i][j] = triangle[i][j] + dp[i - 1][j - 1];
			}
			else
			{
				dp[i][j] = triangle[i][j] + MAX(dp[i - 1][j - 1], dp[i - 1][j]);
			}
		}
	}

	int max = 0;
	for (int j = 1; j < n + 1; j++)
	{
		if (max < dp[n][j])
		{
			max = dp[n][j];
		}
	}

	printf("%d", max);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ