알고리즘 :: 큰돌 :: Chapter 7 - DP :: 백준 1932번 정수 삼각형

Embedded June·2023년 10월 7일
0
post-thumbnail

문제

문제 링크

해설

  • [y][x][y + 1][x][y + 1][x + 1] 두 요소로 타고 내려갈 수 있습니다.
  • 1층은 원소가 하나밖에 없기 때문에 항상 최댓값을 가집니다.
  • 2층부터는 위 두 요소 중 더 큰 값으로 최댓값으로 초기화하면서 한 층씩 내려가면 됩니다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
    int N;
	cin >> N;
	
    vector<vector<int>> A(N), DP(N);
    for (int n, i = 0; i < N; ++i) {
    	for (int j = 0; j <= i; ++j) {
			cin >> n;
			A[i].push_back(n);
			DP[i].push_back(0);
		}
	}
	DP[0][0] = A[0][0];
	for (int y = 0; y < N - 1; ++y) {
		for (int x = 0; x <= y; ++x) {
			DP[y + 1][x] = max(DP[y + 1][x], DP[y][x] + A[y + 1][x]);
			DP[y + 1][x + 1] = max(DP[y + 1][x + 1], DP[y][x] + A[y + 1][x + 1]);
		}
	}
	int ans = 0;
	for (int x = 0; x < N; ++x) ans = max(ans, DP[N - 1][x]);
	cout << ans;
}

소스코드 링크

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글