[프로그래머스 / C++] 정수 삼각형 : DP
https://programmers.co.kr/learn/courses/30/lessons/43105
문제 풀이
가장 기본적인 DP문제인 것 같다.
DP를 푸는 방법은 2가지가 존재한다.
- 점화식을 이용하는
Bottom-Up
방식- 직관적으로 알 수 있는 시작점은 미리 dp배열에 저장해놓는다.
- 점화식에서 재귀(dfs), 메모이제이션을 사용하는
Top-down
방식.- 직관적으로 알 수 있는 지점이 dfs를 중지 시키는 지점
입력값인 triangle
배열을 살피면 다음과 같다.
dp[i][j]
를 (i,j) 좌표까지의 경로중, 가장 큰 숫자 합이라고 지정하자. 점화식은 다음과 같아진다.
dp[i][j]
=max(dp[i-1][j]
,dp[i-1][j-1]
) +triangle[i][j]
(단, j=0이거나 J=i 일 때는 조건 추가)
코드
1) Bottom-Up
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX=501;
int dp[MAX][MAX];
int solution(vector<vector<int>> triangle) {
int answer = 0;
//초기 지정.
dp[0][0]=triangle[0][0];
for(int i=1;i<triangle.size();i++){
for(int j=0;j<=i;j++){
//1) 행에서 젤 왼쪽인 경우엔 바로 위에꺼
if(j==0) dp[i][j]=dp[i-1][j]+triangle[i][j];
//2) 행에서 젤 오른쪽인 경우엔 왼쪽 위에꺼
else if(j==i) dp[i][j]=dp[i-1][j-1]+triangle[i][j];
//나머지
else dp[i][j]=max(dp[i-1][j-1], dp[i-1][j])+triangle[i][j];
answer=max(answer,dp[i][j]);
}
}
return answer;
}
2) Top-bottom
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX=501;
int dp[MAX][MAX];
int tmp[MAX][MAX];
int dfs(int r, int c){
//✨dfs를 멈추는 지점 -> 직관적으로 알 수 있는 지점!
if(r==0&&c==0) return tmp[0][0];
//✨메모이제이션. 이미 계산된 결과가 있는 경우 저장 된 값 반환
if(dp[r][c]>0) return dp[r][c];
//1) 행에서 젤 왼쪽인 경우
if(c==0) return dp[r][c]=dfs(r-1,c)+tmp[r][c];
//2) 행에서 제일 오른쪽인 경우
if(c==r) return dp[r][c]=dfs(r-1,c-1)+tmp[r][c];
//3) 나머지
else return dp[r][c]=max(dfs(r-1,c),dfs(r-1,c-1))+tmp[r][c];
}
int solution(vector<vector<int>> triangle) {
int answer = 0;
// triangle을 dfs의 인자로 넘기면 시간초과 나버림!
for(int i=0;i<triangle.size();i++){
for(int j=0;j<=i;j++){
tmp[i][j]=triangle[i][j];
}
}
// 제일 밑 행
for(int i=0;i<triangle.size();i++){
answer=max(answer, dfs(triangle.size()-1, i));
}
return answer;
}
Author And Source
이 문제에 관하여([프로그래머스 / C++] 정수 삼각형 : DP), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inryu/프로그래머스-C-정수-삼각형-DP저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)