[백준][dp] 1932 정수 삼각형 c++ 구현

목차

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

보기 전에 참고하면 좋을 것 같습니다

https://be-senior-developer.tistory.com/19

[DP] 동적 계획법 알고리즘 c++ 설명

 

 

 

문제 접근 방법

동적계획법 판단

 

최적부분 구조를 만족하는가?

그 전의 값들을 더해 최댓값을 만드므로 더 작은 문제로 만들 수 있으므로 만족한다.

 

중복되는 문제가 있는가?

두 수를 선택하는 중복된 문제가 존재하므로 만족한다.

 

 

 

문제 접근 과정 및 설명

• 위에서 아래로 큰 것을 선택하며 내려가면 여러 반례들에 직면한다.
• 아래서 위로 올라가는데 큰 것을 선택해서 누적하고 싶다.
• 누적할 것이 여러개다 점화식을 통해 이 전의 값에 누적시키자

 

• 누적 과정

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

 

 

• 5번째줄에서 더 큰 것을 선택하여 4번째 줄에 누적

        7
      3   8
    8   1   0
  7   12   10  9
4   5   2   6   5

 

 

• 4번째줄에서 더 큰 것을 선택하여 3번째 줄에 누적

        7
      3   8
    20   13  10
  7   12   10  9
4   5   2   6   5

 

 

• 3번째줄에서 더 큰 것을 선택하여 2번째 줄에 누적

         7
      23   21
    14   13  10
  6   12   10  9
4   5   2   6   5

 

 

• 2번째줄에서 더 큰 것을 선택하여 1번째 줄에 누적

         30
      23   21
    14   13  10
  6   12   10  9
4   5   2   6   5

 

 

 

코드구현

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
vector<int> Tri[20000];

int main() {
	int n, i, y, num, x=0, j;
	cin >> n;
	for (i = 0; i < n; i++) {
		for (j = 0; j <= i; j++) {
			cin >> num;
			Tri[i].push_back(num);    
		}
	}
	
	for (y = n - 2; y >= 0; y--) {        //아래서부터 올라온다.
		for (x = 0; x < Tri[y].size(); x++) {       //열의 크기만큼 반복한다
			Tri[y][x] += max(Tri[y+1][x], Tri[y+1][x + 1]);     //더 큰 수를 더해준다.
			}
	}
	
	cout << Tri[0][0];

}

 

점화식을 발견하는 것이 정말 어렵다..  동적 프로그래밍은 갈 길이 멀다..ㅠㅠ