백준 2096 내려가기 c++ [컴공과고씨]

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

2096번: 내려가기

 

문제 간단 정리

n * 3 개의 행렬 칸이 있고 각 칸에는 숫자가 적혀 있음.

맨 위 부터 출발 하여 내려오는데 바로 아래와 한 칸 대각선으로만 이동 가능함.

이 때 얻을 수 있는 최대, 최소 점수를 구하시오.

 

문제 해결 방법

이 문제 같은 경우 위에서 내려온다는 생각을 하지말고 도착할 칸이 위에서 내려오는 점수를 받는 다고 생각하면 쉽다.

이런식으로 첫번째 칸은 점수를 바로 위와 그 옆에서 밖에 올 수 없기 때문에 이 두 칸을 비교해서 더 큰 수에서 오는 것으로 하면 된다.

그러면 첫 번째 칸에 최대 점수를 넣기 위해서는 그냥 바로 위와 그 옆 점수를 비교해서 더 큰 수를 현재 칸 점수와 더해주면된다. 마찬가지로 가운데는 위 3개를 전부 비교해주며 된다. 3번째 칸도 올 수 있는 칸 두 개의 점수를 비교 해주고 현재 칸을 더해주면 결국 이렇게 내려오면 각 칸의 최대값을 얻게 되고 이 3개 중 가장 큰 것을 찾으면 그 사다리에서 얻을 수 있는 최대 값이 된다. 결국 다이나믹 프로그래밍을 이용한 문제인 것이다.

 

전체 코드

#include <iostream>
using namespace std;
int n;
int arr[3]; // 현재 칸 점수
int mn_dp[3] = {0}; // 각 칸 최소값 기록
int mx_dp[3] = {0}; // 각 칸 최대값 기록
int mn(int a, int b){ // 최소 값 리턴
    if(a>b)
        return b;
    return a;
}
int mx(int a, int b){ // 최대 값 리턴
    if(a<b)
        return b;
    return a;
}
int main(){
    cin >> n;
    int temp0; // 윗 줄 첫번째 칸
    int temp1; // 윗 줄 두번째 칸
    int temp2; // 윗 줄 세번째 칸
    for (int i = 1; i <= n; i++){
        cin >> arr[0] >> arr[1] >> arr[2]; // 현재 칸 점수 
        // 최소 값 기록
        temp0 = mn_dp[0]; // 윗 줄 첫 번째 칸 
        temp1 = mn_dp[1]; // 윗 줄 두 번째 칸
        temp2 = mn_dp[2]; // 윗 줄 세 번째 칸
 
        // 서로 비교 후 현재 칸 점수 더함
        mn_dp[0] = mn(temp0, temp1) + arr[0]; 
        mn_dp[2] = mn(temp1, temp2) + arr[2];
        mn_dp[1] = mn(mn(temp0, temp1), temp2) + arr[1];
 
        // 최대 값 기록
        temp0 = mx_dp[0];
        temp1 = mx_dp[1];
        temp2 = mx_dp[2];
 
        mx_dp[0] = mx(temp0, temp1) + arr[0];
        mx_dp[2] = mx(temp1, temp2) + arr[2];
        mx_dp[1] = mx(mx(temp0, temp1), temp2) + arr[1];
    }
    // 마지막 칸 3개 중 가장 큰 값과 작은 값 추출
    cout << mx(mx(mx_dp[0], mx_dp[1]), mx_dp[2]) << " " << mn(mn(mn_dp[0], mn_dp[1]), mn_dp[2]);
    return 0;
}