대엉코딩

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

1. 풀이방법

- 최대 깊이가 500입니다.

- 모든 경우의 수를 모두 구하면 매우 커짐을 알 수 있습니다.

- 점화식을 세우고, 0과 i==j 일때 (한변에서 양 끝은 선택권이 한개씩 뿐) 처리를 따로 해주시면 됩니다.

- 바텀업 방식으로 작성했습니다.

2. 주의사항

- 없음

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

int triangle[500][500];
int dp[500][500];
int n;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			cin >> triangle[i][j];
			dp[i][j] = -1;
		}
	}
	dp[0][0] = triangle[0][0];
	
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i) {
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}
	int maxr = -1;
	for (int i = 0; i < n; i++) {
		maxr = max(dp[n - 1][i], maxr);
	}
	cout << maxr << "\n";
	return 0;
}

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

- 삼각형의 위에서 부터 길을 만들어 각 수 를 더하였을 때 가장 큰 값이 되도록 하는 길을 쫓아가서

- 그 값을 출력하는 문제입니다.

- vector 두개를 이용하여 들어오는 값과 vector 0과 들어오는 값을 비교하여 vector 1에 저장하고

- 그다음 들어오는 값들은 vector 1과 들어오는 값들을 비교하고 더해 vector 0에 저장하는 작업을 반복한 후

- 물론 작업이 끝난 배열은 초기화를 해야 합니다 (그 다음 줄에서 넣어야하므로)

- 마지막에 n의 값에 따라서 vector 0 또는 vector 1 을 내림차순 으로 정렬 한후 index 0의 값을 출력하였습니다.

- 값을 더하고 저장하고 더하고 저장하고 를 반복하는 작업이라고 생각 하시면 될거 같습니다.

- 그리고 각 입력의 처음과 마지막은 비교를 할 필요없이 바로 0번쨰 index그리고 마지막 index랑 더해서 넣으면 됩니다.

<필기>

<코드>