- 문제 (1932번) : 정수 삼각형
- 입력받은 정수삼각형에서 각 층마다 정수를 하나 선택하여 아래층으로 내려올 때 선택된 수의 합이 최대가 되는 합을 출력하는 문제. ( 경로 선택문제 )
- 입력 및 출력
[입력]
- 첫째줄에 삼각형의 크기 n 입력
- 둘째줄 ~ n+1번째줄까지 정수 삼각형 입력 (t)
[입력제한 범위]
- 1 ≤ n ≤ 500 ( 삼각형의 크기 )
- 0 ≤ t ≤ 9,999 & 정수 ( 삼각형을 이루고 있는 각 수 )
[출력]
- 합이 최대가 되는 경로에 있는 수의 합 출력
- 문제 풀이
- 각 단계를 통과할때마다 다음과 같은 3가지 경우로 경로 선택 가능하다.
( i단계, j번째 값까지의 합산값이 저장되는 array : arr[i][j] ) - 배열을 사용해 memoization으로 해결
- 가장 왼쪽의 수를 선택
- 오른쪽 대각선 위에서 내려온 값과 자신을 합산
- 중간에 있는 수를 선택
- 왼쪽 대각선 위 또는 오른쪽 대각선 위에서 내려온 값과 자신을 합산한 값 중 큰 값으로 저장
- 가장 오른쪽의 수를 선택
- 왼쪽 대각선 위에서 내려온 값과 자신을 합산
- 모든 경우의 수를 생각해 2차원 배열에 값을 저장하며 maximum 값을 매번 업데이트해 구한다.
[ 큰 값을 max 변수에 저장 ]
- 최종 코드
