백준 2096 - 내려가기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2096

2096번: 내려가기

다이나믹 프로그래밍과 슬라이딩 윈도우 알고리즘이 합쳐진 문제입니다.

 

문제를 풀기 위해서는 N값을 봐야합니다.

N값이 100,000 까지지만, 메모리 제한이 4MB입니다.

따라서 N칸 만큼 배열을 만드는 것이 아닌, 입력을 받을 때마다, 최대, 최소값을 비교해야함을 알 수 있습니다.

 

입력이 들어올 때마다 최소, 최대값을 비교해야하기에 어떤 방식으로 이루어지는지 확인해보겠습니다.

최댓값을 구하는 방법입니다.

각각의 위치에서 갈 수 있는 곳이 정해져 있음으로 위 그림의 방식을 통해 구할 수 있습니다.

최솟값의 경우도 마찬가지로 같은 방식을 통해 구할 수 있습니다

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>

using namespace std;

int N;
int dp[4][2]; // 0 -> 최대, 1 -> 최소

int Max(int x, int y, int z) {
	return (((x > y) ? x : y) > z) ? ((x > y) ? x : y) : z;
}

int Min(int x, int y, int z) {
	return (((x > y) ? y : x) > z) ? z : ((x > y) ? y : x);
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= 3; i++) {
		cin >> dp[i][0];
		dp[i][1] = dp[i][0];
	}
	for (int i = 1; i < N; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		int copy_max_1 = dp[1][0], copy_max_2 = dp[2][0], copy_max_3 = dp[3][0];
		int copy_min_1 = dp[1][1], copy_min_2 = dp[2][1], copy_min_3 = dp[3][1];
		dp[1][0] = Max(copy_max_1 + x, copy_max_2 + x , 0);
		dp[2][0] = Max(copy_max_1 + y, copy_max_2 + y , copy_max_3 + y);
		dp[3][0] = Max(0, copy_max_2 + z , copy_max_3 + z);
		/////////////////////////////////////////////////////////////////////
		dp[1][1] = Min(copy_min_1 + x, copy_min_2 + x, 9999999);
		dp[2][1] = Min(copy_min_1 + y, copy_min_2 + y, copy_min_3 + y);
		dp[3][1] = Min(9999999, copy_min_2 + z, copy_min_3 + z);
	}
	int mini = dp[1][1], maxi = dp[1][0];
	for (int i = 1; i <= 3; i++) {
		mini = min(mini, dp[i][1]);
		maxi = max(maxi, dp[i][0]);
	}
	cout << maxi << " " << mini;
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요