[C++/BOJ] 백준 1932 정수 삼각형 (DP)

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

1932번: 정수 삼각형

 

 

백준 티어 : 실버1

 

 

 

 

 

 

=> 삼각형이 입력되고 (0,0)을 시작으로 삼각형의 마지막줄까지 최대가 되는 경로를 찾아 출력하는 문제이다.

 

 

 

해설 : 

DP를 이용하여 풀이하면된다.

숫자를 저장할 이차원배열(mp) 과 최대 경로를 저장할 이차원배열(cache)

을 정의한후

재귀를 이용한 dp로 풀이한다.

 

 

 

정답 코드 :

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int n;

int mp[501][501],cache[501][501];

int func(int y, int x){

     if(y==n-1) return mp[y][x]; //y좌표가 n-1이라는 것은 마지막줄이라는 의미이다. [그림 1참고]

     int &ret = cache[y][x]; //ret이라는 별명을 지어준다.

     if(ret!=-1) return ret;  // 변경되어있는 경우 그대로 반환

     return ret = max(func(y+1,x), func(y+1,x+1))+mp[y][x]; //[그림2참고]

}

int main(){

     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);  // cin과 cout의 속도를 빠르게 하는 코드

     cin >> n;

     for(int i=0;i<n;i++){ // 삼각형 모양의 입력을 받는 for문

          for(int j=0;j<i+1;j++){  //사각형이 아니므로 j는 i만큼 입력받는다. 즉 j < i+1이다.

               cin >> mp[i][j];

          }

     }

     memset(cache,-1,sizeof(cache));  // memset을 이용하기위해서는 cstring은 include해주어야한다.

// cache의 모든 값을 -1로 초기화한다.

     func(0,0); //mp배열의 [0][0]에서부터 시작하므로 

}

 

추가 설명 : 

if(y==n-1) return mp[y][x];

=>마지막 줄일 경우 더할수있는 것이 더이상 없으므로 해당 배열의 mp값 자체를 반환합니다.

그림1

return ret = max(func(i+1,x), func(i+1,x+1))+ mp[y][x];

=>  

 [아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.]

 

그림2

그림과 같이 바로 아래 또는 아래의 옆으로만 이동이 가능하므로

max(func(y+1,x), func(y+1,x+1))를 이용해 아래 두 값중 최대값을 골라

원래 좌표의 mp[y][x] 값을 더해준다.

 

cache[y][x] 에는 경로의 최댓값이 저장되어있는데

 

출력하면 이와같이 저장되어있다.

n-1일경우 그냥 mp의 값이 반환되므로 초기값인 -1에서 변경되지않고

그 이후로부터 해당경로의 최댓값이 저장된다. [아래부터 저장]

즉 main에서 func(0,0)을 부르는 이유도 이것이다.

 

이것은 재귀를 사용하였는데

재귀를 짤때는 지금상황과 다음단계를 정의하는 함수만 생각하면 편하다.

 

문제후기 : 

 

dp가 어떻게 생각하면 많이 헷갈린다.

가볍게 현재와 다음, 기저조건만 생각해서 풀어야겠다는 생각이든다.