[백준 알고리즘] 1932번: 정수 삼각형
May 05, 2020
1932번: 정수 삼각형
문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.접근 방법:
삼각형에 빗변에 해당하는 행의 가장 첫 열과 마지막 열은 이전 행의 첫 열과 마지막 열과의 누적합이다. 따라서 각 행을 순회하면서 가장 첫 요소와 마지막 요소는 이전 행의 처음과 마지막 값에서 현재 값을 더해준다. 중간 값은 우리가 최댓값을 구해야하기 때문에 두가지 경우의 수, 즉 현재 노드를 기준으로 왼쪽 위에 있는 노드의 값과의 합과 오른쪽 위에 있는 노드의 값과의 합을 구해서 더 큰 값을 저장해주면 각 경우의 수들 중에 가장 큰 값이 저장된다. 마지막 N 행에 도달하면 각각의 경우의 수를 모두 고려한 점수들이 각 노드에 배치된다. 여기서 최댓값을 구해서 출력해주면 끝.
통과 코드:
#include <iostream>
#include <vector>
using namespace std;
int main (){
int N;
cin >> N;
vector<vector<int>> triangle (N, vector<int>(N, -1));
vector<vector<int>> dp (N, vector<int>(N, 0));
for(int i = 1 ; i <= N ; i++){
for (int j = 0 ; j < i ; j++){
cin >> triangle[i-1][j];
}
}
for (int i = 1 ; i <= N ; i++){
for (int j = 0 ; j < i ; j++){
if (i == 1) dp[i-1][j] = triangle[i-1][j]; // 첫 행은 그대로 가자
else if (j == 0) dp[i-1][j] = dp[i-2][j] + triangle[i-1][j]; // 각 행의 첫 노드는 바로 위에 있는 노드의 값과의 합
else if (j == i-1) dp[i-1][j] = dp[i-2][j-1] + triangle[i-1][j]; // 각 행의 마지막 노드는 이전행의 마지막 노드의 값과의 합
else{
dp[i-1][j] = max(dp[i-2][j-1]+triangle[i-1][j], dp[i-2][j]+triangle[i-1][j]); // 중간 노드는 왼쪽 위에 있는 값과의 합, 그리고 오른쪽 위에 있는 값과의 합 중 더 큰 값
}
}
}
int max_score = 0;
for (int i = 0 ; i < N ; i++){
max_score = max(dp[N-1][i], max_score); // 가장 큰 값 구하기
}
cout << max_score;
return 0;
}
