문제
https://school.programmers.co.kr/learn/courses/30/lessons/43105
문제 설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
[[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;
}
밑에서 출발하여 위로 올라가는 방식을 사용한 분들도 계셨다.
두 숫자 중 큰 숫자를 위에 있는 수에 더하는 방식이었다.
탑 다운 마냥 재귀로 푸는 경우는 보았었는데 이런 방식으로도 할 수 있다는 것이 신기해서 포스팅해보았다.
'코테 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/C#] 점프와 순간 이동 (0) | 2024.04.11 |
---|---|
[프로그래머스/C#] 괄호 회전하기 (0) | 2024.03.27 |
[프로그래머스/C++] 구명보트 (0) | 2024.03.18 |
[프로그래머스/C#] 최대공약수와 최소공배 (0) | 2024.03.13 |
[프로그래머스/C#] 문자열 나누기 (0) | 2024.03.13 |