정수 삼각형

오늘의 문제

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

정수 삼각형

접근 방식

• dp문제로, 아래쪽의 입장에서 가장 큰것을 받은 결과를 저장한다. 일종의 Greedy이다.
• 그리고 가장 큰 수를 출력하면 된다. 당연히 맨 아래층의 값이 제일 클것이다.

나의 풀이

#include <iostream>
using namespace std;
const int MAX = 500;
int arr[MAX][MAX];
int n;

// 정수 삼각형
int solution(){
    int answer = 0;
    int dp[MAX][MAX];
    dp[0][0] = arr[0][0];
    for(int i=1;i<n;i++){
        for(int j = 0;j<i+1;j++){
            if(j == 0)
                dp[i][j] = dp[i-1][j]+arr[i][j];
            else if(j == i)
                dp[i][j] = dp[i-1][j-1]+arr[i][j];
            else
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) +arr[i][j];
            answer = max(dp[i][j], answer);
        }
    }
    return answer;
}

다른 풀이

//DP
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, in; cin >> n;
	int dp[502] = { 0, }; int tmp[502];
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			cin >> in;
			if (j == 0) tmp[0] = dp[0] + in;
			else if (j == i - 1) tmp[j] = dp[j - 1] + in;
			else tmp[j] = max(dp[j - 1] + in, dp[j] + in);
		}
		for (int j = 0; j < i; j++) {
			dp[j] = tmp[j];
		}
	}
	int res = 0;
	for (int i = 0; i < n; i++) res = max(res, dp[i]);
	cout << res;
	return 0;
}

배울 점

• 같다. 다른점은 왜 for문을 두개 돌리셨는지 모르겠다.