[프로그래머스/C++] 정수 삼각형

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

 

문제 설명

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

 

 

 

코드

---

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    for(int i=1;i<triangle.size();i++){
        for(int j=0;j<triangle[i].size();j++){
            int temp;
            if(j==0){
                temp=triangle[i-1][j];
            }
            else if(j==triangle[i].size()-1){
                temp=triangle[i-1][j-1];
            }
            else{
                temp=max(triangle[i-1][j], triangle[i-1][j-1]);
            }
            triangle[i][j]+=temp;
        }
    }
    int idx = triangle.size()-1;
    for(int i=0;i<triangle[idx].size();i++){
        answer=max(answer, triangle[idx][i]);
    }
    return answer;
}

 

 

 

 

풀이

---

동적계획법(Dynamic Programming)을 사용하여 풀었다.

triangle 배열 위에서부터 현재 위치에서 나올 수 있는 최대값을 찾는다는 방식으로 구하면 된다.

 

 

예를 들어 triangle[1][0] 위치에서 나올 수 있는 최대값은 3+7로 10이며, triangle[1][1] 위치에서 나올 수 있는 최대값은 8+7로 15가 나온다.

 

이제 triangle[2][n] 위치에서 나올 수 있는 최대값을 알아보자.

triangle[2][0]과 triangle[2][2] 위치에서는 나올 수 있는 값이 한 가지밖에 없기 때문에 각각 10+8=18, 15+0=15가 된다.

반면 triangle[2][1] 위치에서는 나올 수 있는 값이 두 가지가 된다.((1, 0) 값을 더하거나 (1,1) 값을 더하거나)

이 때 triangle[2][1]에서의 최대값을 구하기 위해서는 두 가지 선택지 중에서 더 큰 수를 더해야 한다. 그러므로 더 큰 값인 15를 더한 16이 최대값이 된다.

 

위의 코드도 이와 같은 방식으로 구현되어있다.

 

첫 번째거나 마지막일 경우 선택지는 하나밖에 없으므로 위와 같이 구현.

 

 

그 외의 경우는 선택지가 두 가지이므로 둘 중 큰 값을 선택.

 

 

선택한 값은 기존 위치의 값에 +

 

 

삼각형 맨 끝에 있는 숫자들을 비교하며 최대값을 찾은 뒤 return.

 

 

 

다른 사람 풀이

---

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> t) {
    int answer = 0;

    for (int i = t.size() - 1; i > 0 ; i--)
    {
        for (int j = 0; j < t[i].size() - 1; j++)
        {
            if (t[i][j] > t[i][j + 1])
            {
                t[i - 1][j] += t[i][j];
            }
            else
            {
                t[i - 1][j] += t[i][j + 1];
            }
        }
    }

    answer = t[0][0];

    return answer;
}

 

밑에서 출발하여 위로 올라가는 방식을 사용한 분들도 계셨다.

두 숫자 중 큰 숫자를 위에 있는 수에 더하는 방식이었다.

탑 다운 마냥 재귀로 푸는 경우는 보았었는데 이런 방식으로도 할 수 있다는 것이 신기해서 포스팅해보았다.