백준 : 1932번 정수 삼각형(c++)

백준 링크

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

1932번: 정수 삼각형

코드 풀이

이전에도 한 번 풀었던 문제여서 쉽게 풀었던거 같다.

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

위와같이 삼각형이 주어진다고 하면

3가지 부분만을 나눠서 탐색하면된다

1. 제일 왼쪽은 무조건 아래로 더해준다

2. 가장 오른쪽은 무조건 오른쪽 대각선으로 더해준다.

3. 가운데 값들은 위 왼쪽 값 + 현재의값 or 위에 값 + 현재의값 중 큰 값을 고르면 된다.

이 방식으로 구현해주고 최대값을 구해주면 완성

여기서 주의해야할 점은 Answer의 초기값으로 맨 위의 값을 넣지 않으면 답이 제대로 나오지 않으니 주의

코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<vector<int>> vecTriangle;
    vector<vector<int>> vecAdd;

    int N;

    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        vector<int> vec;
        vec.resize(i + 1);
        vecAdd.push_back(vec);
        for (int j = 0; j < i + 1; ++j)
        {
            cin >> vec[j];
        }
        vecTriangle.push_back(vec);
    }

    vecAdd[0][0] = vecTriangle[0][0];
    // Answer의 초기값을 무조건 맨 처음 값으로 넣어주어야한다.
    int Answer = vecAdd[0][0];

    for (int i = 1; i < N; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            // 제일 왼쪽 이전 + 현재 숫자 합
            if (j == 0)
            {
                vecAdd[i][j] = vecAdd[i - 1][j] + vecTriangle[i][j];
            }
            // 제일 오른쪽 이전 + 현재 숫자 합
            else if (i == j)
            {
                // 여기서 j - 1을 해주는 이유는 하나 위에 칸은 j개수가 한칸 적기 때문
                vecAdd[i][j] = vecAdd[i - 1][j - 1] + vecTriangle[i][j];
            }
            else
            {
                // 위 왼 + 현재 위치 , 위 + 현재 위치 중 큰값 선택
                vecAdd[i][j] = max(vecAdd[i - 1][j - 1] + vecTriangle[i][j], vecAdd[i - 1][j] + vecTriangle[i][j]);
            }

            Answer = max(Answer, vecAdd[i][j]);
        }
    }

    cout << Answer;

    return 0;
}