[BOJ] 백준 1932. 정수 삼각형

▶문제설명

[BOJ] 백준 1932. 정수 삼각형

https://www.acmicpc.net/problem/1932

▶Hint

---

DP 문제이다.

예시로 주어진 크기가 5인 정수 삼각형은 아래와 같다.

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

입력으로 주어질 때는 아래와 같이 주어진다.

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

입력으로 주어진 정수 삼각형을 아래와 같이 2차원 배열에 저장할 수 있다.

dp	[0]	[1]	[2]	[3]	[4]	[5]
[0]	0	0	0	0	0	0
[1]	0	7	0	0	0	0
[2]	0	3	8	0	0	0
[3]	0	8	1	0	0	0
[4]	0	2	7	4	4	0
[5]	0	4	5	2	6	5

숫자 7이 저장된 dp[4][2]를 예로 들면, 왼쪽 위에 있는 숫자는 dp[3][1]이 되고 오른쪽 위에 있는 숫자는 dp[3][2]가 된다.

이것을 일반화시키면 dp[r][c]의 왼쪽 위에 있는 숫자는 dp[r-1][c-1]이 되고, 오른쪽 위에 있는 숫자는 dp[r-1][c]가 된다.

우리는 최상단에서 아래로 내려오면서 합을 최대로 만들어야 하므로

dp[r][c] = MAX( dp[r-1][c-1] + dp[r][c]  , dp[r-1][c] + dp[r][c] ) 

위와 같은 식을 세워 답을 구할 수 있다.

[1][1]에서부터 [5][1] ~ [5][5]까지 식을 이용해 값을 구하면 아래와 같은 결과를 얻게 된다.

dp	[0]	[1]	[2]	[3]	[4]	[5]
[0]	0	0	0	0	0	0
[1]	0	7	0	0	0	0
[2]	0	10	15	0	0	0
[3]	0	18	16	15	0	0
[4]	0	20	25	20	19	0
[5]	0	24	30	27	26	24

가장 아래 행에 저장된 누적합 중 가장 큰 수를 출력하면 정답이 된다.

▶Solution