백준 1932 정수 삼각형

< 백준 1932 정수 삼각형 - 마포 코딩박 >

사용한 알고리즘: DP


 정수 삼각형의 각 구성 성분을 입력으로 주고, 맨 윗줄 부터 맨 아랫줄 까지 주어진 규칙을 따라 경로를 선택하며 해당 경로의 성분값을 더했을 때 구할 수 있는 최대 합을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~6)
 'dp[i][j] : (i,j) 까지 도달할 때 얻을 수 있는 최대 성분합' 이라고 설정하였습니다.

(2) (코드 15~20)
 시작점의 dp값=시작점 자신 임을 생각하여 초기값 dp[1][1] = A[1][1] 을 설정한 뒤, 각 dp값들을 찾아 주었습니다.

(3) (코드 22~23)
 삼각형을 이루는 성분들은 음수가 아니므로 맨 밑줄의 dp값 중 하나가 구하고자하는 최댓값입니다.

	#include <bits/stdc++.h>
	using namespace std;
	int A[505][505], N, M;
	// dp[i][j] : (i,j) 성분에 도착했을 때 얻을 수 있는 최대 합
	int dp[505][505];
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; ++i)
	for (int j = 1; j <= i ; ++j)
	cin >> A[i][j];
	// 초기값 설정
	dp[1][1] = A[1][1];
	// dp값 설정
	for (int i = 2; i <= N; ++i)
	for (int j = 1; j <= i ; ++j)
	dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + A[i][j];
	for (int i = 1; i <= N; ++i)
	M = max(M, dp[N][i]);
	cout << M << '\n';
	return 0;
	}

view raw BOJ 1932.cpp hosted with ❤ by GitHub