[프로그래머스 Lv.3] 정수 삼각형

 

DP - 정수 삼각형

 

Solution ) 

 

밑으로 내려갈 수록 쌓여 내려간다. DFS 로 풀 수도 있겠지만, 경우의 수가 너무 많아지므로 효율이 떨어진다.

DP 방식, 즉 기억해서 써먹기 알고리즘으로 가야한다.

 

쉽게 접근하고자 삼각형을 배열(표) 형식으로 바꿔본다.

7	0	0	0	0
3	8	0	0	0
8	1	0	0	0
2	7	4	4	0
4	5	2	6	5

(Triangle 이중 배열)

* 빈칸으로 보일 수 있는 부분은 계산식 수립이 용이하도록 0을 채워넣었다.

 

삼각형을 배열(표)로 만든 것과 동일하게, SumList 라는 이중 배열을 하나 더 만들어주었다.

이 이중 배열의 용도는 해당 칸까지 내려간 수의 Sum, 총 합 값을 기억하기 위해서다.

 

7	0	0	0	0
10	15	0	0	0
18	16	15	0	0
20	25	20	19	0
24	30	27	26	24

(SumList 이중 배열)

*빨간 숫자는 해당 칸에 들어올 수 있는 Sum 값이 두 개일 때, 비교해 최댓값을 채워넣은 칸이다

 

이 때 알 수 있는 점은,

예를 들면 우리가 SumList 4행의 값들을 구하려고 할 때, SumList의 3행과 Triangle 배열의 4행이 각각 보유한 값들만 참고해서 SumList 4행을 구할 수 있다는 점이다.

DFS 로 했다면, 1행부터 마지막 행 까지 다 구해서 또 비교하는 일을 반복해야 했을 것이다.

 

DP의 요점은

1) 반복 작업의 효율화
2) 기억해서 가지고 있다가 써먹기

 

인 것 같다.

 

나도 DP 문제를 많이 풀어본 건 아니지만, 이 문제는 꾸준히 다시 풀어보는게 좋을 것 같아서 기록용으로 남긴다.

 

 

풀이