[백준/BOJ] 1932번 정수 삼각형 (C/C++)

백준 온라인 저지(BOJ) 1932번 정수 삼각형

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

1932번: 정수 삼각형

* 사용언어 : C언어, C++

 

1. 문제

크기가 N인 정삼각형에 각 숫자가 채워져 있음

맨 위층부터 대각선 왼쪽, 오른쪽 둘 중 하나를 선택해서 내려올 때 합이 최대가 되는 경로에 있는 수의 합을 출력 

 

 

2. 풀이

규칙이 명확하게 주어진 문제이기 때문에 bottom-up 방식으로 구현하였습니다.

우선 정사각형을 주어진 그대로 2차원 배열로 입력을 받습니다.

그리고 각 위치의 숫자에 왼쪽 위(x - 1) dp 값과 오른쪽 위(x) dp 값 중 큰 값을 더해서 해당 위치의 dp 값을 구합니다.

 

단, y번째 row에서 0번째 column은 왼쪽 위 숫자가 없고, y - 1번째 column은 오른쪽 위 숫자가 없으므로

앞서 언급한 규칙과 다르게 처리해주어야 합니다.

 

 

추가로 처음 개발할 때는 삼각형의 값을 tri라는 배열에 입력하고 dp 배열을 따로 두었었습니다.

그런데 생각해보니 dp 배열 하나로 처리가 된다는 것을 깨닫고 코드를 수정하여 메모리를 줄였습니다. (3,064KB → 2,088KB)

관련 내용은 아래 코드로 설명 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1932_정수 삼각형
2008KB	16ms
*/
#include <cstdio>

const int LM = 500;
int dp[LM][LM], N, res;

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

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int y = 0; y < N; ++y)
	for (int x = 0; x <= y; ++x)
		scanf("%d", &dp[y][x]);

	for (int y = 1; y < N; ++y) {
		dp[y][0] += dp[y - 1][0];
		dp[y][y] += dp[y - 1][y - 1];

		for (int x = 1; x < y; ++x) dp[y][x] += max(dp[y - 1][x - 1], dp[y - 1][x]);
	}

	for (int x = 0; x < N; ++x) {
		if (dp[N - 1][x] > res) res = dp[N - 1][x];
	}
	printf("%d\n", res);
	return 0;
}