문제 정보
백준 ( BOJ ) 1932 정수 삼각형
문제 풀이 : 동적 계획법
문제 출처 : https://www.acmicpc.net/problem/1932
시작 Thinking
문제는 두가지 풀이방법이 있습니다.
우선은 여기서는 공간이 정말 넓기 때문에 상관 없지만,
메모리 부족 문제를 야기 할 것 같은 경우에는, 큐라던가, 일자형 배열 두개를 사용한다던가 하는 방식으로
하면 됩니다.
[f]
[a] [b]
[c][d][e]
여기서 차근차근 늘려가볼까요
[f]
[a + f] [b + f]
[c] [d] [e]
우선은 한번 시행은 다음과 같습니다. 크게 별다를게 없어요
그럼 다음 실행은?
[a + f] [b + f]
[c + a + f] [d + ( a+ f) or (b + f) ] [e + b + f]
다음과 같이 됩니다.
맨 왼쪽과 맨오른쪽 끝은 계산 할 필요가 없습니다.
그리하여 둘중 하나를 번외로 처리 해 주고, 남은쪽은, 0과 비교하게 하여 처리 해주면 됩니다.
하는방법은, 맨 처음은 그대로 더해주고,
그 뒤로는, 자신의 윗사람과 윗사람의 왼쪽 사람 중 더 큰쪽에 붙어주면 됩니다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
queue<int> block;
int main() {
int n;
int temp;
cin >> n;
vector<vector<int>> result(n ,vector<int>(n,0));
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
cin >> temp;
result[i][j] = temp;
}
}
for (int i = 0; i < n; i++) {
if(i != 0 )
result[i][0] += result[i - 1][0];
for (int j = 1; j <= i; j++) {
temp = result[i - 1][j - 1] > result[i - 1][j] ? result[i - 1][j - 1] : result[i - 1][j];
result[i][j] += temp;
}
}
temp = 0;
for (int i = 0; i < n; i++) {
if (temp < result[n-1][i])
temp = result[n-1][i];
}
cout << temp;
return 0;
}