https://www.acmicpc.net/problem/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번째 행까지 해준다.
-
n-2행부터
[소스 코드]
#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;
}
'Coding Test > Problem_solving' 카테고리의 다른 글
[백준] 11055_가장 큰 증가 부분 수열 (C++) (0) | 2021.11.05 |
---|---|
[백준] 22557_ 가장 긴 짝수 연속한 부분 수열(small) (c++) (0) | 2021.11.04 |
[백준] 계단오르기 2579 c++ (0) | 2021.11.03 |
[백준] 20300_서강 근육맨 (C++) (0) | 2021.07.02 |
[백준] 1758_알바생 강호(python) (0) | 2021.07.01 |