[C++ / 1932] 정수 삼각형

문제

1932번: 정수 삼각형

---

문제 설명

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구해야 한다.

 

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

---

풀이 방식

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

다음 n = 5일때 다음과 같은 삼각형이 있다고 하자.

 

다음 풀이의 핵심은 이전 값의 계산을 축척하여 경로와 max값을 파악할 수 있다는 점이다.

 

1층의 7은, 2층의 3, 8를 가르킬 수 있다. 그럼으로 7을 3과 8에 각각 더해준다.

이때 2층의 10, 15는 자연스레 그 결과에 경로를 가지게 있게 된 것이다.

즉, 이전의 결과가 반영이 된 것이다.

 

계속해보자.

2층의 3은, 3층의 8, 1을 가르킬 수 있다. 또한 2층의 8은, 3층의 1, 0을 가르킬 수 있다.

그럼으로 각각 가르칠수 있는 값에 수를 더하다 보면, 3층의 2번째 값인 1은 11 또는 16이라는 값을 가질 수 있다.

이렇게 값을 두가지 가질 수 있는 경우 우리의 목표는 최대값을 가지는 경로를 파악하기 위함이므로 최대값만 남긴후 다른 값은 무시한다.

그럼 3층에는 18, 16, 15 라는 값이 된다. 

 

이러한 과정을 반복하면 된다.

n층 까지 이러한 계산 과정이 완료 된다면, 마지막 층의 값은 자연스레 이전에 대한 결과값이 반영되어 현재와 같은 결과가 나온 것이다.

그럼으로 마지막 층의 값 중 최대값을 고른다면 그것이 합이 최대가 되는 경로를 택했을 때의 결과 값이다.

아래 경우의 경우 30이 이에 해당한다.

---

솔루션

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

using namespace std;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;

  vector<vector<int>> v;
  vector<vector<int>> ans;

  for (int i = 1; i < n + 1; i++)
  {
    vector<int> a(i);
    v.push_back(a);
    ans.push_back(a);
  }

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < i + 1; j++)
    {
      cin >> v[i][j];
    }
  }

  ans[0][0] = v[0][0];

  for (int depth = 0; depth < n - 1; depth++)
  {
    for (int i = 0; i < v[depth].size(); i++)
    {
      for (int j = i; j <= i + 1; j++)
      {
        if (ans[depth + 1][j] != 0)
        {
          ans[depth + 1][j] = max(ans[depth + 1][j], ans[depth][i] + v[depth + 1][j]);
        }
        else
        {
          ans[depth + 1][j] = ans[depth][i] + v[depth + 1][j];
        }
      }
    }
  }

  int max = *max_element(ans[n - 1].begin(), ans[n - 1].end());
  cout << max;

  return 0;
}

---

여담

for을 3중으로 겹쳐써서 12ms의 러닝타임이 나왔다.

c++로 문제를 푼 사람들의 러닝타임을 보니 12ms가 느린 속도는 아니지만, 8ms로 더 빠르게 풀 수 있는 알고리즘이 존재하였다.

 

DP와 관련된 문제를 풀어보았는데.. 값들 간의 연관성이나 규칙을 잘 찾아내는 것이 중요한 것 같다고 느꼈다.

 

또한 vector를 2차원으로 쓰는게 의외로 귀찮다는 것을 알게 되었다. 다만 동적할당이 가능하여 자주 애용할 것 같다.