[#57][알고리즘] 숫자삼각형
백준 > 숫자삼각형
문제 링크(https://www.acmicpc.net/problem/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줄까지 숫자 삼각형이 주어진다.
출력
첫째 줄에는 최대가 되는 합을 출력한다.
예제 입력
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
예제 출력
30
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int test, k = 0;
vector<vector <int>> input, answer;
cin >> test;
answer.resize(test);
input.resize(test);
for (int i = 0; i < test; i++) {
k++;
input[i].resize(test);
answer[i].resize(test);
//2차원 벡터에
for (int j = 0; j < k; j++) {
cin >> input[i][j];
if (i == 0 && j == 0)
answer[i][j] = input[i][j];
}
}
for (int i = 1; i < test; i++) {
for (int j = 0; j < i+1; j++) {
if (j == 0) {
//맨 처음 원소
answer[i][j] = answer[i - 1][j] + input[i][j];
}else if (i == j) {
//맨 끝 원소
answer[i][j] = answer[i - 1][j-1] + input[i][j];
}else {
//중간
answer[i][j] = max(answer[i - 1][j - 1]+input[i][j], answer[i - 1][j]+input[i][j]) ;
}
}
}
//최대값 찾기
int max = 0;
for (int i = 0; i < input[0].size(); i++) {
if (max < answer[test - 1][i]) {
max = answer[test - 1][i];
}
}
cout << max << endl;
return 0;
}
| cs |
answer에는 더한 값을 저장
양쪽 끝 값에 대한 처리
j == 0일 때 : answer의 바로 위 값 + 현재 값 = answer[i-1][j] + input[i][j]
i == j일 때 : answer의 왼쪽 위 대각선 + 현재 값 = answer[i-1][j-1] + input[i][j]
중간 값
i = 0 ~ i = j - 1까지 : 왼쪽 위 대각선 + 현재 값 , 바로 위 값 + 현재 값 중 최대
댓글
댓글 쓰기