백준 1932번 정수 삼각형

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

1. 처음에 푼 코드

#include <stdio.h>

int big(int x, int y)//둘 중 더 큰 수를 가리는 함수 big 정의
{
	if (x > y) return x;
	else return y;
}

int main()
{
    int array[501][501] = {0};
    int total[501][501] = {0};
	int n;
	int i, j;
	int max = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= i; j++)
		{
			scanf("%d", &array[i][j]);
		}
	}
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= i; j++)
		{
			total[i][j] = array[i][j] + big(total[i - 1][j - 1], total[i - 1][j]);// 경우의 수를 팍 줄일 수 있는 핵심적인 코드
            원래 2가지 경우가 생길수 있는걸 더 큰걸 고르면서 한가지로 줄인다.
		}
	}
	for (i = 1; i <= n; i++)
	{
		if (max < total[n][i])
		{
			max = total[n][i];
		}
	}
	printf("%d", max);
	return 0;
}

두번째 코드

두개의 배열을 하나로 줄이면서 메모리 사용을 줄이고
big함수 대신 삼항연산자를 사용하여 코드를 좀 더 깔끔하게 만들어 보았다.

#include <stdio.h>

int main()
{
    int array[501][501] = {0};
	int n, i, j, x, y, max = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= i; j++)
		{
			scanf("%d", &array[i][j]);
		}
	}
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= i; j++)
		{
            x = array[i - 1][j - 1];
            y = array[i - 1][j];//x,y가 없으면 밑의 줄이 너무 길어져 코드의 가독성이 떨어진다.
			array[i][j] += (x > y ? x : y);
		}
	}
	for (i = 1; i <= n; i++)
	{
		if (max < array[n][i])
		{
			max = array[n][i];
		}
	}
	printf("%d", max);
	return 0;
}

세번째 코드

배열의 절반이 낭비되고 있는데 이 낭비되는 메모리를 줄여보고자 한다.

1. 배열을 두 줄 사용하는 코드

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int* array = calloc(501,sizeof(int));
	int* brray = calloc(501,sizeof(int));
	int* temp;
	int n, i, j, max = 0;
	scanf("%d", &n);
	scanf("%d", array+1);
	for (i = 2; i <= n; i++)
	{
		for (j = 1; j <= i; j++)
		{
			scanf("%d", brray + j);
		}
		for (j = 1; j <= i; j++)
		{
			brray[j] += array[j - 1] > array[j] ? array[j - 1] : array[j];
		}
		temp = array;
		array = brray;
		brray = temp;
	}
	for (i = 1; i <= n; i++)
	{
		if (max < array[i])
		{
			max = array[i];
		}
	}
	printf("%d", max);
	return 0;
}

2.배열을 한 줄 사용하는 코드

#include <stdio.h>

int main()
{
	int array[501] = {0};
	int i ,j, n, x, max;
	max = 0;
	scanf("%d", &n);
	scanf("%d", &array[499]); // 짜다보니 계속 왼쪽 칸이 하나씩 더 필요하게 되어 오른쪽부터 시작하게 됨.
	for (i = 2; i <= n; i++)
	{
		for (j = 0; j < i; j++)
		{
			scanf("%d", &x);
			x += array[500 - i + j] > array[500 - i + j + 1] ? array[500 - i + j] : array[500 - i + j + 1];
			array[500 - i + j] = x;
		}
	}
	for (i = 1; i <= n; i++)
	{
		if (max < array[500 - i]) max = array[500 - i];
	}
	printf("%d", max);
	return 0;
}