💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

🧺출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

🔋예제 입출력

🔮예제 입력1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

🔮예제 출력1

30

💉문제 분석

🔋분류

다이나믹 프로그래밍(DP)

🔋난이도

실버I

💉문제 풀이

🔋해법

우선 문제유형이 DP이기때문에 일정한 규칙을 찾아야합니다.
우선은 높이는 1~N까지입니다.
만약 이중 임의의 높이를 i(y)라고 하고, 길이를 j(x)라고할때,

[i][j]에 들어갈 최대크기는 [i-1][j]와 [i-1][j-1]에서 현재 입력된 값(소스코드에서는 x라는 변수)과의 합의 최댓값으로 결정됩니다.

만약에 위 점화식을 실제 실행시켜보시면 실제 그래프상으로는 아래와같이 나옵니다.

           7
        10   15
      18   16   15
   20   25   20    19
24   30   27    26    24

점화식을 이용한 위 표에서의 임의의 높이를 i(y)라고 할때,
이때 i(y)는 i번째높이까지 가는데 최대가 되는 수의 합이 됩니다.

따라서 이 문제에서 구해야하는 답은 N번째높이에서 가장 큰 값을 가지는 원소인 30이 되게됩니다.

🔋소스코드

#include <bits/stdc++.h> //1932

constexpr int MAX = 501;

int adj[MAX][MAX];

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);

	int N;
	std::cin >> N;

	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= i; ++j) {
			int x;
			std::cin >> x;
			adj[i][j] = std::max(adj[i - 1][j], adj[i - 1][j - 1]) + x;
		}
	}

	int result = adj[N][0];
	for (int i = 1; i <= N; ++i) if (result < adj[N][i]) result = adj[N][i];

	std::cout << result;
}

이번 문제는 살짝쿵 재미있었습니다.
dp많이 연습해야되겠습니다.
아직 꼬꼬마네용..

💉마치며...

궁금한 부분있으시면 댓글로 질문주세요~~