1932

1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net DP 문제다. 정수 삼각형의 맨 꼭대기에서 밑으로 내려오면서 선택된 수의 합이 최대가 되는 경로에 있는 수의 합을 구하는 문제. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 시간 제한이 2초이므로 약 4,000만 번 연산이 가능한데, n의 범위는 500정도밖에 되지 않았다. 그래서 O(N^2)도 여유롭기 때문에 그냥 다 계산하면 되겠다라는 생각이 먼저 들었다. 먼저 dp 배열을 2차원 리스트로 만들어준다. dp[i][j]에는 i번째 층에서 j번째 숫자를 선택했을 때..