알고리즘
[알고리즘 문제해결전략] TRIANGLEPATH - 삼각형 위의 최대 경로
[생각의 흐름] 1. 완전 탐색을 하게 되면 2^100이라 타임 아웃 발생 2. 동적계획법을 통해 캐싱 3. 캐싱은 cache[Y][X][sum]을 먼저 생각했으나 sum의 경우 100000 * 100이 되어 메모리 초과발생 4. cache[Y][X]가 가능한지 고민 => Y, X일 때 최대값만 구하면 된다. => 아래(Y+1, X)와 오른쪽 아래(Y+1, X+1) 의 값 중 큰 값을 선택 /* https://www.algospot.com/judge/problem/read/TRIANGLEPATH */ #include #include #include using namespace std; const int MAX_SIZE = 101; int n; int triangle[MAX_SIZE][MAX_SIZE]; ..
