[C++] 백준 1932 정수 삼각형

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void DP(int n, vector<vector<int>>& m);

int main()
{          
    ios::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    int n = 0;
    cin >> n;

    vector<vector<int>> m(n);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            int temp;
            cin >> temp;
            m[i].push_back(temp);
        }
    }

    DP(n, m);

    sort(m[n - 1].begin(), m[n - 1].end());

    cout << m[n - 1][n - 1];


    return 0;
}

void DP(int n, vector<vector<int>> &m)
{
    if (n >= 2)
    {
        m[1][0] += m[0][0];
        m[1][1] += m[0][0];
    }
    if (n > 2)
    {
        for (int i = 2; i < n; i++)
        {
            m[i][0] += m[i - 1][0];
            
            for (int j = 1; j < i; j++) //겹쳐지는 부분은 합을 구해서 큰 것을 넣는다.
            {
                int left = m[i - 1][j - 1] + m[i][j];
                int right = m[i - 1][j] + m[i][j];

                m[i][j] = max(left, right);
            }

            m[i][i] += m[i-1][i - 1];
        }
    }
}

풀이

1. DFS나 BFS를 사용한다면 모든 경우의 수를 탐색하게 되므로 시간초과가 나게된다.

2. 위와 같이 각 경우의 합의 최대 값을 구해주게 되면 더욱 빠르게 값을 구할 수 있다.

    7

   3 8

  8 1 0

 2 7 4 4

4 5 2 6 5

 

                   7
              10      15
        18       (16)     15
    20      (25)    (20)     19

24  (25, 30) (27, 22) (26, 25)  24

 

이와 같은 규칙이 있다.

1줄은 그대로

2줄은 1줄과 수의 합

3줄부터 가운데 수는 

  1

 1 2

1 2 3

이므로

줄수가 i고 각 수가 j일때 3줄의 2는 아래와 같다.

[i - 1][j - 1] + [i][j] 와 [i - 1][j] + [i][j]

1,1              2,2           1,2        2,2

이것의 합을 비교하여 큰 것을 해당 수 [i][j]에 넣게되면 그 전까지의 최대 값을 구할 수 있다.

3. 마지막 줄의 최대 값을 구하기 위해 내림차순으로 정렬해준다.

 

 

 

- DP배열을 사용한 풀이

void DP(int n, vector<vector<int>>& m);

int main()
{          
    ios::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    int n = 0;
    cin >> n;

    vector<vector<int>> m(n + 1);

    for (int i = 0; i < n + 1; i++)
    {
        for (int j = 0; j < n + 1; j++)
        {
            if(j == 0)
                m[i].push_back(0);
            else if (j > i)
                m[i].push_back(0);
            else
            {
                int temp;
                cin >> temp;
                m[i].push_back(temp);
            }
            
        }
    }

    DP(n, m);

    sort(m[n].begin(), m[n].end());

    cout << m[n][n];


    return 0;
}

void DP(int n, vector<vector<int>> &m)
{
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < i; j++) //겹쳐지는 부분은 합을 구해서 큰 것을 넣는다.
        {
            int left = m[i - 1][j - 1] + m[i][j];
            int right = m[i - 1][j] + m[i][j];

            m[i][j] = max(left, right);
        }
        m[i][i] += m[i-1][i - 1];
    }
}

 

 

 

 

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

1932번: 정수 삼각형