코후닝

알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 【 풀이 】 삼각형의 규칙을 구하면 된다. 2차원 배열 dp에 입력 받고, 각 칸까지 선택된 수의 합을 각 칸에 다시 저장한 2차원 배열을 dp라고 하자. dp[1][1] = dp[1][1] dp[2][1] = dp[1][1] + dp[2][1], dp[2][2] = dp[1][1] + dp[2][2] 이다. 3번째 층부터, 가운데의 수들은 양쪽 대각선에 저장된 숫자 중 가장 큰 값과 더해져야 한다. 즉, dp[3][1]..