백준 1932번 C++

백준 1932번 정수 삼각형
https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

정답 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin>>n;
	vector<int> temp;
	vector<vector<int>> triangle;
	int one;
	
	for(int i = 1; i<=n; i++){
		temp.clear();
		for(int j = 0; j<i; j++){
			cin>>one;
			temp.push_back(one);
		}
		triangle.push_back(temp);
	}
	
	
	for(int i = n-1; i>0; i--){
		// j를 0부터 n-2까지 키우며
		for(int j = 0; j<triangle[i].size()-1; j++){
			//j와 j+1중 크기가 더 큰걸 누적해 더해나간다.
			if(triangle[i][j]>=triangle[i][j+1]){
				triangle[i-1][j] += triangle[i][j];
			}
			else{
				triangle[i-1][j] += triangle[i][j+1];
			}
			
		}
		
	}

	
	cout<<triangle[0][0];
	
}

문제 폴이
다이나믹 프로그래밍을 이용해서 풀 수 있는 문제입니다. 이중 반복문을 돌리면서 배열 아래쪽부터 탐색해서 큰 값을 윗줄에 더해주면서 풀어주면 됩니다. 그리드 알고리즘으로 풀게 되면 오답 처리되니 주의 바랍니다.