#1932 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

실버 1의 문제이다. 언제쯤 dp문제 푸는 감을 익힐수 있을까 ㅜ.

#include <iostream>
#include <algorithm>
using namespace std;

int dp[501][501];
int triangle[501][501];

int main()
{
  freopen("input.txt","r",stdin);
  int maxnum=0;
  int n; //삼각형의 크기
  cin>>n;

  for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
      cin>>triangle[i][j];
    }
  }

  dp[1][1]=triangle[1][1];
  //왼쪽
  for(int i=2;i<=n;i++){
    dp[i][1]=dp[i-1][1]+triangle[i][1];
  }

  //오른쪽
  for(int i=2;i<=n;i++){
    dp[i][i]=dp[i-1][i-1]+triangle[i][i];
  } 

  //이외
  for(int i=3;i<=n;i++){
    for(int j=2;j<n;j++){
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+triangle[i][j];
    }
  }

  for(int i=1;i<=n;i++){
    if(dp[n][i]>maxnum)
      maxnum=dp[n][i];
  }

  cout<<maxnum<<'\n';
}

이 문제도 점화식을 찾는데 오랜 시간이 걸렸다. 아니 사실 점화식을 도저히 찾지 못하겠어서 질문게시판에 올라온 어느 분의 점화식을 슬쩍 했다.

 

dp[1][1] = 7

dp[2][1] = dp[1][1] + 3,  dp[2][2] = dp[1][1] + 8

dp[3][1] = dp[2][1] + 8,  dp[3][2] = max( dp[2][1], dp[2][2] )  + 1

.

.

.

 

삼각형의 왼쪽 모서리, 오른쪽 모서리, 그 외의 부분 이렇게 3부분으로 나누어 점화식을 구했다.

 

왼쪽: dp[i][j] = dp[i-1][j] + triangle[i][j]

오른쪽 :  dp[i][j] = dp[i-1][j-1] + triangle[i][j]

그 이외 부분 : max( dp[i-1][j] + dp[i-1][j-1] ) + triangle[i][j]

로 나타낼 수 있다. 

 

따라서 왼쪽, 오른쪽, 그 이외의 부분 을 나누어 for문을 돌리고 dp배열에 값을 저장한다. 

이렇게 되면 마지막 n번째 행에 최종 값들이 저장되어있을 것이고, 마지막에 n행에만 대해서 최대값을 구해주면 그 값이 정답이 된다. 

 

?그냥 해보면 되는데 왜 하지 않았을까?