알고리즘 스터디

프로그래머스 코테 연습 : 정수 삼각형

Reddish 2023. 1. 22. 00:03

정수 삼각형

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항
  • 삼각형의 높이는 1 이상 500 이하입니다.
  • 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
입출력 예triangleresult
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

접근

 여러가지 경우를 생각해 봤다. 일단 dp인걸 알고 풀었지만, '거쳐간', '최댓값' 등의 키워드를 통해서 문제 유형이 dp라고 생각 할 수 있었을것 같다. dp가 작은 문제를 해결함으로서 큰 문제를 해결 하는 개념이므로, 작은 부분을 "거쳐" 더 큰 부분의 결과를 도출하는~~~이런 식으로 생각을 해서 풀었을 것 같다.

 문제 처음 보면서 여러가지 경우를 생각했다. dp의 작은 문제를 어디서 볼지 고민했다. 삼각형 모양인, 7, 3, 8을 작은 문제로 볼지, 아니면 하나하나를 고려해야할 지, 혹은 맨 밑인 4, 5에서 부터 시작해야 할지 등..여러 생각이 나왔다.

 세부적인 부분에 집중하면서 문제를 다시 보았을 때, 문제가 삼각형에서 밑부분에서 시작해 위로 올라가는게 아닌 위에서 부터 아래로 내려온다는 느낌을 받았다. 7에서 부터 시작해 그 밑에 있는 3과 8에 전달 하고, 3에서의 여태까지의 합이 8과 1에게 전해지고.... 이런 식이라는 느낌을 받았다. 그렇다면 삼각형 단위가 아닌, 각 수가 단위라는 것을 알았다.

 

핵심 코드

    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < triangle[i].size(); j++)
        {
            if(j == 0)
            {
                arr[i][j] = triangle[i][j] + arr[i - 1][j];
            }
            else if(j == triangle[i].size() - 1)
            {
                arr[i][j] = triangle[i][j] + arr[i - 1][j - 1];
            }
            else
            {
                arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + triangle[i][j];
            }

            if(arr[i][j] > answer)
            {
                answer = arr[i][j];
            }
        }
    }

이중 for문에 많은 if문까지 좀 복잡하다 느낄 수 있을수도 있다. 그 안의 실상은 그렇게 어려운 편이 아니다. 인덱스를 잘 설정하면 사실 끝나는 문제이다.

arr 배열은 합을 나타내 주는 배열이다. 편의상 누적합이라고 할 것이다. 삼각형 위치에서의 최대의 합을 나타내 준다. 핵심 코드 전에 arr[0][0]은 시작 전 triantle[0][0] 값을 넣어줄 것이다. 그러고 나서, 다음줄로 넘어가서 전 줄의 최대값을 들고와 자기와 더해준다. 이때, 전 줄의 최댓값은 인덱스가 [i - 1][j - 1] 또는 [i - 1][j] 이여야 할 것이다. 

3  8

8  1  0 과 같이 배열이 주어질 것이기 때문에,  1의 관점에서 인덱스가 [i - 1][j - 1] 또는 [i - 1][j] 이여야 할 것이다.

 

위에서의 예시를 잠깐 들고와서 생각을 해보자.

7                  -> triangle[0][0] = arr[0][0]

3  8              -> 3은 arr[0][0]에 자기 자신(triangle[1][0])을 더한 값이다. 8 또한 arr[0][0] + 자기 자신(triangle[1][1])의 합이다.

8  1  0          -> 8은 가장 가장자리이므로, 3 누적합과 자기 자신을 더한다. 그럼, 7 + 3에다가 자기자신 8을 더한 값인 18이 누적합 arr[2][0]의 값일 것이다. 1은 3과 8에서 누적합을 받을 수 있다. 그래서, 둘 중 더 큰 값을 들고와서 그 큰 값과 자기 자신을 더한다. 그렇다면, (7 + 3)이랑 (7 + 8)중에 더 큰 수인 (7 + 8)와 1을 더해 arr배열에 넣어준다. 0은 가장자리 수이므로, 8에서만 받아서 7 + 8 + 0 = 15가 arr에 저장 된다.

 

이런 식으로, 우리는 세 가지 경우를 생각 할 수 있다.

왼쪽 가장 자리일 경우 : arr[i][j] = triangle[i][j] + arr[i - 1][j]

오른쪽 가장 자리의 경우 : arr[i][j] = triangle[i][j] + arr[i - 1][j - 1]

중간에 오는 경우 : arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + triangle[i][j] 

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle)
{
    int answer = 0;
    int arr[501][501] = {0};

    int N = triangle.size();
    arr[0][0] = triangle[0][0];
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < triangle[i].size(); j++)
        {
            if(j == 0)
            {
                arr[i][j] = triangle[i][j] + arr[i - 1][j];
            }
            else if(j == triangle[i].size() - 1)
            {
                arr[i][j] = triangle[i][j] + arr[i - 1][j - 1];
            }
            else
            {
                arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + triangle[i][j];
            }

            if(arr[i][j] > answer)
            {
                answer = arr[i][j];
            }
        }
    }
   
    return answer;
}

다시 설명하자면, arr은누적합을 나타낸다.

 

느낀 점

오랜만에 풀어보는 dp였는데 생각보다 나름 괜찮게 풀었었다. dp를 배열과 재귀로 접근하는 경우가 많은데 for문 두개로도 충분히 가능하다 생각해서 풀었더니 가능했다. 나도 이제 실력이 많이 늘었음을 가늠할 수 있었는데 구현이 너무 귀찮았다. 그래도 나름 다 풀면서 보람도 차고 해서 기분이 좋았다 ㅎㅎ

 

저작자표시 비영리 (새창열림)