[BOJ] 1932.정수삼각형.py.cpp (DP 기초)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

입력이 아래와 같을 때,

        7

      3   8

    8   1   0

  2   7   4   4

4   5   2   6   5

정수 삼각형을 이차원배열로 저장해보면

7

3 8

8 1 0

2 7 4 4 

4 5 2 6 5

로 표현할 수 있다.

      

보면, dp[i][j]는 dp[i-1][j-1]과 dp[i-1][j]중 큰 값에 arr[i][j]를 더하는 점화식을 세워볼 수 있다.

이런 경우 테두리를 0으로 두고 저장하는 것이 편한데,

이렇게 하는 경우 index 접근 에러를 방지할 수 있다.

0 0 0 0 0 0

0 7 0 0 0 0

0 3 8 0 0 0

0 8 1 0 0 0

0 2 7 4 4 0

0 4 5 2 6 5

0 0 0 0 0 0

다시 정수 삼각형이 dp[][]에 저장되는 동작을 살펴보면

        7

      3   8

    8   1   0

  2   7   4   4

4   5   2   6   5

먼저 첫 줄에 7의 상단은 비어있으므로

        7

둘째 줄에 3의 상단은 0과 7중 더 큰 값 7에 3을 더한 10이 되고,

8의 상단은 7과 0중 더 큰 값 7에 8을 더한 15가 된다.

          7

      10   15

셋째 줄에 8의 상단은 0과 10 중 큰 값 10에 8을 더한 18이 되고,

1은 상단의 10과 15 중 큰 값 15에 1을 더한 16

0은 상단의 15와 0 중 큰 값에 0을 더한 15가 된다.

           7

      10    15

    18   16   15

넷째 줄에 2의 상단 0과 20중 큰 값 18에 2를 더한 20

7의 상단 18과 16중 큰 값 18에 7를 더한 25

...

           7

      10    15

    18   16   15

 20   25   20   19

...

#. Python Code

N = int(input())
arr = [[0 for _ in range(N+1)] for __ in range(N+1)]
dp = [[0 for _ in range(N+1)] for __ in range(N+1)]
 
for i in range(1, N+1):
    tmp = list(map(int, input().split()))
    for j in range(1, i+1):
        arr[i][j] = tmp[j-1]
 
for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]
 
print(max(dp[-1]))

#. Cpp Code

#include <cstdio>
#include <algorithm>
using namespace std;
 
int dp[501];
 
int main(void)
{
    int n, val, i, j;
    //freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++) {
        for (j = i; j >= 1; j--) {
            scanf("%d", &val);
            dp[j] = max(dp[j] + val, dp[j - 1] + val);
        }
    }
 
    printf("%d\n", *max_element(dp+1, dp+1+n ));
 
    return 0;
}

python으로 할 때는 2차원 배열 2개를 이용해서 했었는데,

c++로 더 최적화적인 방법을 찾아 구현해보았다.

line 5) 전역변수 dp[] 선언

         * 최대 n이 크다면 배열로 vector로 동적할당해도 되지만, 여기서는 최대 n이 500으로 작기때문에 전역변수로 하는게

           시간은 똑같은데 메모리면에서 효율적이다.

line 13~18) 1~n 줄까지 반복

line 14~17) 해당 줄 최대 index부터 1까지 반복

* 첫 번째 줄은 정수 1개, 두 번째 줄은 정수 2개, n 번째 줄은 정수 n개

line 15) 정수 입력

line 16) 해당 index의 상단에 있는 수 + 입력 정수, 좌상단에 있는 수 + 입력정수 중 큰 값을 저장

(i=1, j=1) 7 입력 : max(0+7, 0+7)

0 7

(i=2, j=2) 3 입력 : max(0+3, 7+3)

0 7 10

(i=2, j=1) 8 입력 : max(7+8, 0+8)

0 15 10

(i=3, j=3) 8 입력 : max(0+8, 10+8)

0 15 10 18

(i=3, j=2) 1 입력 : max(10+1, 15+1)

0 15 16 18

(i=3, j=1) 0 입력 : max(15+0, 0+0)

0 15 16 18

...

* 이런 알고리즘을 생각해내기까지 얼마나 많은 과정을 거쳐야 할까.. 화이팅..!