[C++] 백준 1932번 : 정수 삼각형

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

1932번: 정수 삼각형

---

문제 풀이

 tri 배열에 입력받은 값을 저장한다. 

문제에서 입력받은 값들, 즉 원본을 따로 저장하라고 하지 않았기 때문에 바로 배열 값들을 수정하면서 확인하면 된다. 

따라서, 2번째 행부터 확인하여 윗 값과 윗 값의 다음 값과 비교해서 더 큰 값을 해당 배열 값에 더하면 된다.

초기 값 → 연산 후

연산이 끝난 이후 마지막 행의 값 중 가장 큰 값을 출력하면 된다. 

연산을 할 값의 위치가 가장자리인지 아닌지에 따라 나눌 수 있지만 굳이 그렇게 하지 않아도 연산결과는 같기 때문에 코드를 줄이기 위해서 경우를 나누진 않았다.

느낀 점

 값을 입력받는 부분, 즉 시작 단계부터 헤맸다. 그리곤 값을 따로 저장해야한다는 생각 때문에 한 시간 정도는 또 헤맨 거 같다. 다른 분들의 코드를 보고 굳이 원본을 유지할 필요가 없음을 알고 그 이후는 쉽게 푼 것 같다. 아직도 접근법이 많이 미숙함을 보이는 문제였다.

코드

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

int n;
int tri[501][501];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0 ; j <=i ;j++){
			cin >> tri[i][j];
		}
	}
	
	for (int i = 1; i < n;i++) {
		for (int j = 0; j <= i;j++) {
			tri[i][j] += max(tri[i - 1][j], tri[i - 1][j - 1]);
		}
	}
	int value = 0;
	for (int i = 0; i < n; i++) {
		if (value < tri[n - 1][i]) value = tri[n - 1][i];
	}
	cout << value;
}