[백준] 1932_정수 삼각형 (c++)

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

1932번: 정수 삼각형

 

[규칙]

1. 맨 위의 층부터 시작

2. 아래의 있는 수 중 최대가 되는 경로 찾기

3. 대각선 왼쪽 또는 오른쪽에 있는 것만 선택 가능

4. 삼각형 크기 500이하

5. 시간제한 2초

 

[실패 원인]

• 이것도 마찬가지로 마음 편하게 DFS로 풀었더니 시간 초과가 났다. 
  
  • 시간이 2초나 되는데 오류가 난 것이다. ㅋㅎㅋㅎ, 세상에,,,
  • 그래서 백준의 '질문 검색'버튼을 이용해서 다른 분들도 시간 초과가 났나 보았다. 
  • 보니깐 문제가 '메모이제이션(Memoization) 을 이용해야 한다고 한다. 
    • 메모이제이션이란?
      • 구글에 검색해서 보았더니, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하는 것이라고 한다. 
      • 참고 : https://wondytyahng.tistory.com/entry/memoization-%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98
      • 근데 이걸 보고 이걸 저장할 값이 있나 생각을 해보았다. 
      • 그전에, 이걸 DFS를 사용할 필요가 있나?라는 생각을 해보니 답이 나왔다. 

 

[풀이 설명]

• 먼저 마지막 행 위의 행부터 시작하기로 했다. 

  • 

    n-2행부터
    • 자기 아래의 값, 아래 +1 값 중 큰 값을 자신과 더했다. 
    • 옆에 그림을 보면 알 수 있다. 
    • 첫 번째를 설명해보면, 젤 마지막 행에서 4와 5중에서는 5가 크므로, 2(자기 자신)과 5를 더해준다. 
    • 이렇게 0번째 행까지 해준다. 

 

[소스 코드]

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

int main() {
	int n; //삼각형의 크기 
	int Triangle[501][501];
	int max_num = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			cin >> Triangle[i][j];

	for (int row = n - 2; row >= 0; row--)
		for (int col = 0; col <= row; col++)
			Triangle[row][col] += max(Triangle[row + 1][col], Triangle[row + 1][col + 1]);

	cout << Triangle[0][0];

	return 0;
}