My Profile

김형훈

안녕하세요.
김형훈입니다.

백준 2096 내려가기

백준 2096 내려가기

2022년 11월 26일

2022년 11월 26일

cpp, 다이나믹 프로그래밍

문제

문제

풀이

풀이

각각의 줄에 대해 세개의 숫자 중 하나를 고를 때의 최소 점수를 dp를 이용해 구현한다.

이때 문제에서 요구하는 메모리 제한을 잘 의식해야 한다.

코드

코드

#include <bits/stdc++.h>
#define MAX(A,B) (A>B?A:B)
#define MIN(A,B) (A<B?A:B)
using namespace std;

int n;
int max_ans[3]; // 최소한의 메모리로 층마다 재사용
int min_ans[3];
int dMAX[3];
int dMIN[3];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=1; i<=n; ++i){
        for(int j=0; j<3; ++j){
            cin >> dMAX[j];
            dMIN[j] = dMAX[j];
        }
        // 각 위치별로 최댓값과 최솟값을 구한다.
        dMAX[0] += MAX(max_ans[0],max_ans[1]);
        dMAX[1] += MAX(MAX(max_ans[0],max_ans[1]),max_ans[2]);
        dMAX[2] += MAX(max_ans[1],max_ans[2]);

        dMIN[0] += MIN(min_ans[0],min_ans[1]);
        dMIN[1] += MIN(MIN(min_ans[0],min_ans[1]),min_ans[2]);
        dMIN[2] += MIN(min_ans[1],min_ans[2]);
        // 가장 큰 값 갱신
        for(int j=0; j<3; ++j){
            max_ans[j] = dMAX[j];
            min_ans[j] = dMIN[j];
        }
    }
    cout << MAX(MAX(max_ans[0],max_ans[1]),max_ans[2]) << ' ' << MIN(MIN(min_ans[0],min_ans[1]),min_ans[2]);
}
결과Permalink

결과

결과

Copyright © 2024 Hyunghoon Kim