dp9 [백준] - 1932 정수 삼각형 (Python) 문제 출처 : www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 풀이: 우선 이 문제 같은경우는 다음과 같은 조건을 고려해서 점화식을 짜야한다. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 여느 DP 문제와 같이 점화식을 먼저 세워봣다. DP[i] = level i에서 얻을 수 있는 최대 합 이라고 생각하고 각각의 경우를 생각해봣다. (단, tri는 삼각형의 수를 들고 있는 자료구조) 이후 다음과 같이 각 단계에 대한 DP를 생각해보니 DP를 2차원으로 짜야.. 2021. 3. 6. 이전 1 2 3 다음 반응형
