문제
백준과 프로그래머스 두 사이트에 모두 있는 문제로 난이도는 각각 실버1, Lv3이다.
프로그래머스
백준
문제설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항
삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
입출력 예
triangle : [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
result : 30
문제분석
삼각형의 꼭대기에서 바닥까지 이동하는 경로중에서 지나가는 숫자의 합한값의 최대값을 구하는 문제이다.
Dynamic Programing(동적계획법)
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
해결방식은 크게 Bottom-up과 Top-Down방식이 존재한다.
Bottom-up방식은 작은 문제부터 해결하며 큰 문제를 해결하는 방식이며 반복문을 사용한다.
Top-Down은 큰 문제를 작은 문제로 나누어 해결하는 방식이며 재귀를 사용한다.
자세한 내용은 이 동영상에서 잘 설명해준다.
해결방법
일단 해결방법은 위에서부터 내려가는 방식과 아래서부터 올라가는 방식을 사용할 수 있다.
각각 내려가거나 올라가면서 현재의 위치에 현재까지 지나온 숫자들의 최대값을 저장한다고 한다.
문제의 예시로 주어진 삼각형 4번째 줄의 7을 이용해 설명을 해보겠다.
내려가는 방식에서 현재위치에 이전위치로는 8,1이 가능한데 둘의 최대값을 비교하여 더큰 최대값을 가지는 8을 더해서 저장한다. 그리고 바닥까지 동일한 방식을 수행한 후에 값을 맨아래줄의 최대값들을 비교하여 최대값을 구하면된다.
올라가는 방식을 사용하면 5,2 중 큰 값인 5를 현재위치에 더한 값을 저장하면된다. 꼮대기까지 도달했을때 꼭대기의 값이 바로 최대값이 된다.
두 방식중 올라가는 방식을 사용하면 최대값을 바로 구할 수 있기에 올라가는 방법을 사용하여서 문제를 해결하였다.
코드
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> triangle) {
int n=triangle.size();
vector<int> pre,tmp;
pre=triangle[n-1];
for(int i=n-1;i>0;i--)
{
tmp=triangle[i-1];
for(int j=0;j<i;j++)
{
tmp[j]+=pre[j] > pre[j+1] ? pre[j] : pre[j+1];
}
pre=tmp;
}
return pre[0];
}파이썬 연습을 위해 파이썬으로도 해결해 보았다.
def solution(triangle):
size=len(triangle)
for i in range(size-1,0,-1):
for j in range(i):
triangle[i-1][j]+=triangle[i][j] if triangle[i][j]>triangle[i][j+1] else triangle[i][j+1]
return triangle[0][0]
프로그래머스 기준으로 Lv3문제였기에 풀어보았던 이모티콘 할인행사보다 어려울거라 예상했는데 그리 어려운 문제는 아니였고 DP문제를 연습해 보기에 적당한 문제라고 생각된다.
+파이썬 삼항 연산자 사용법 : [on_true] if [expression] else [on_false]
