백준 1932 정수 삼각형

< 백준 1932 정수 삼각형 - 마포 코딩박 >

사용한 알고리즘: DP


 정수 삼각형의 각 구성 성분을 입력으로 주고, 맨 윗줄 부터 맨 아랫줄 까지 주어진 규칙을 따라 경로를 선택하며 해당 경로의 성분값을 더했을 때 구할 수 있는 최대 합을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~6)
 'dp[i][j] : (i,j) 까지 도달할 때 얻을 수 있는 최대 성분합' 이라고 설정하였습니다.

(2) (코드 15~20)
 시작점의 dp값=시작점 자신 임을 생각하여 초기값 dp[1][1] = A[1][1] 을 설정한 뒤, 각 dp값들을 찾아 주었습니다.

(3) (코드 22~23)
 삼각형을 이루는 성분들은 음수가 아니므로 맨 밑줄의 dp값 중 하나가 구하고자하는 최댓값입니다.