[C언어] 삼각형 경로 최대 합 찾기

문제를 나중에

첨부하도록 하겠습니다..

 

삼각형 모양의 정수 배열을 받아

아래로 내려가는 경로에서 가장 큰 합을 찾는 문제입니다.

 

/**
* 정수 삼각형
* 삼각형 꼭대기에서 바닥까지 이어지는 경로에서 합이 가장 큰 경우 찾기
*/
#include <stdio.h>
int solution(int(*arr)[5], int col, int row);
int get_max(int* arr);
int main()
{
	int result = 0;
	
	result = solution((int[][5]) { {7}, { 3, 8 }, { 8, 1, 0 }, { 2, 7, 4, 4 }, { 4, 5, 2, 6, 5 } }, 5, 5);
	printf("%d\n", result);

	return 0;
	
}
int solution(int (*arr)[5], int col, int row)
{
	int i = 0, j = 0, k = 0, max = 0;
	int sumList[5] = {0,};
	
	arr[i][j] = arr[0][0];
	for (i = 1; i < row; i++) {
		for (j = 0; j < col; j++) {
			if (arr[i][j] == 0) continue; 
			if (j == 0) { 
				arr[i][j] += arr[i-1][j];
			}
			else if (j == i) {
				arr[i][j] += arr[i-1][j-1];
			}
			else {
				int com1 = arr[i - 1][j - 1];
				int com2 = arr[i - 1][j];
				int max_value = com1 > com2 ? com1 : com2;

				arr[i][j] = arr[i][j] + max_value;
			}			
			
		}
		memcpy(sumList, arr[i], sizeof(arr[i]));
	}

	/*더한 값들 중 최댓값 구하기*/
	max = sumList[0];
	for (int i = 0; i < sizeof(sumList) / sizeof(sumList[0]); i++) {
		if (max < sumList[i])
			max = sumList[i];
	}
	
	return max;
}

 

피드백, 댓글 환영

ㅎ.ㅎ