[백준] #1932 정수삼각형

[백준] #1932 정수삼각형 - (DP)

i009727 2020. 3. 2. 15:28

(문제

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

1932번: 정수 삼각형

문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는

www.acmicpc.net

목표

정수로 이루어진 삼각형이 주어질때 맨위에서 대각선으로만 내려가면서 수를 선택하여 최대값을 구하는문제

풀이

DP로 풀이

점화식: dp[i][j] = max(dp[i][j], dp[i][j-1]) + dp[i][j];

즉, 단계마다 이전 단계 왼쪽위, 오른쪽위 수를 확인하여 큰값에 현재 자신의 값을 더한값으로 dp배열을 재구성한다.

코드

1. 재귀를 이용하여 구현

: 2020.03.17 다시 풀다보니까 재귀로 풀려서 추가함

////재귀를 이용하여 구현
#include <iostream>
#include <cstring>
#define MAX 501

using namespace std;

int N;
int arr[MAX][MAX];
//dp[i][j] = i행 j열에 해당하는 최대값을 저장
int dp[MAX][MAX];

int func(int row, int col) {
	// cout << "Func call: " << row << ", " << col << '\n'; 
	if (row == -1)
		return 0;
	int &ref = dp[row][col];
	if (ref != -1)
		return ref;
	//맨 왼쪽 열인경우: 선택지 1개
	if (col == 0)
		ref = max(ref, func(row-1, col) + arr[row][col]);
	//맨 오른쪽 열인경우: 선택지 1개
	else if (col == row)
		ref = max(ref, func(row-1, col-1) + arr[row][col]);
	//중간에 위치한 열인경우: 선택지 2개
	else {
		ref = max(ref, func(row-1, col-1) + arr[row][col]);
		ref = max(ref, func(row-1, col) + arr[row][col]);
	}
	return ref;
}
int main() {
	cin >> N;

	for (int i=0; i<N; ++i) {
        for (int j=0; j<=i; ++j) {
			cin >> arr[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	int result = -1;
	//맨 아래 행에서 최대값을 찾아 출력
	for (int i=0; i<N; ++i) {
		result = max(result, func(N-1, i));
	}
	cout << result;
	cout << endl;

	for (int i=0; i<N; ++i) {
        for (int j=0; j<=i; ++j) {
			cout << dp[i][j] << " ";
		}
		cout << '\n';
	}
}

2. 반복을 이용하여 구현

#include <iostream>
#include <vector>
#define MAX_TRI 501

using namespace std;

int H;
int dp[MAX_TRI][MAX_TRI];

int func1() {
    int res = 0;
    for (int i=1; i<=H; ++i) {
        for (int j=1; j<=i; ++j) {
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + dp[i][j];
            if (res < dp[i][j])
                res = dp[i][j];
        }
    }
    return res;
}

int main() {
    cin >> H;
    for (int i=1; i<=H; ++i) {
        for (int j=1; j<=i; ++j) {
            cin >> dp[i][j];
        }
    }
    cout << func1();
}