문제
https://programmers.co.kr/learn/courses/30/lessons/43105
코드
cpp
#include <string>
#include <vector>
#include <algorithm>
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++){
if(j==0) triangle[i][j]+=triangle[i-1][j];
else if(j==triangle[i].size()-1) triangle[i][j]+=triangle[i-1][j-1];
else {
triangle[i][j]+=max(triangle[i-1][j-1],triangle[i-1][j]);
}
}
}
answer=*max_element(triangle[triangle.size()-1].begin(),triangle[triangle.size()-1].end());
return answer;
}python
def solution(m, n, puddles):
answer = 0
dp = [[0]*(m+1) for _ in range(n+1)]
dp[1][1] = 1
for x, y in puddles:
dp[y][x] = -1
for i in range(1, n+1):
for j in range(1, m+1):
if dp[i][j] == -1:
dp[i][j] = 0
continue
if i == j == 1:
continue
dp[i][j] = dp[i-1][j]+dp[i][j-1]
return dp[n][m]%1000000007풀이
기본 dp문제입니다 정수로된 삼각형이 있고 꼭대기부터 바닥까지의 경로중 거쳐간 숫자가 가장 큰 값을 리턴하는 문제입니다. 아래칸으로 이동할때는 대각선으로 한칸씩만 이동 가능한게 뽀인트죠
2번째 줄부터 위에서 가져올 수 있는 큰 값을 가져와서 더해가면 됩니다.
삼각형의 2번째 줄부터 구하면 되는데 만약 현재 숫자가 왼쪽이나 오른쪽 가장 끝 숫자라면 바로 위의 끝 숫자를 더해줍니다 아닌 경우에는 자기 대각선 한칸 위의 숫자중 큰숫자를 가져와서 현재 숫자에 더해줍니다
문제에서 예시로 주는 삼각형인데 예를 들어서 위에서부터 세번째 줄의 8의 경우 위에서 가져올 수 있는 숫자가 3밖에 없죠 1의 경우에는 3이랑 8중에 큰 숫자를 더해주고 0은 8을 더해주는겁니다. 이런 식으로 더해주다 보면 dp테이블이 완성이 되고 제일 큰값을 리턴해주면 됩니다.
7
10 15
18 16 15
20 25 20 19
24 30 27 26 24이중 for문을 다돌면 이렇게 삼각형이 완성이 되겠네요
