1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 31번 문제와 거의 비슷한 문제. DP 테이블을 2차원 리스트로 설정해서 DP 테이블 갱신을 통해 최댓값을 구해주면 된다. 내 풀이 코드 # 1932번: 정수 삼각형 n = int(input()) # 삼각형의 크기 graph = [] # 삼각형을 이루고 있는 수를 저장하는 리스트 for _ in range(n): data = list(map(int, input().split())) graph.append(data) # dp 테이블 dp = [[0] * n for _ in range(n)] # 점화식을 통해 dp 테이블 갱신 for i..
정수삼각형
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번째 숫자를 선택했을 때..
