[BOJ] 2096번 내려가기 (C++)

문제 (https://www.acmicpc.net/problem/2096)

2096번: 내려가기

DP + 슬라이딩 윈도우로 해결한 문제이다. 두 알고리즘 모두 취약해서...ㅎㅎ 다른 코드를 참고하여 풀었다.

 

크기가 3인 배열들 minArr, maxArr, minTmp, maxTmp을 사용했는데, minTmp, maxTmp는 현재 행 이전까지의 결과를 저장해둔 배열이다.

- 첫 번째 행의 값들은 최솟값이자 최댓값이므로 4개의 배열에 모두 삽입해준다.

- 첫 번째 행이 아닐 경우에는 minTmp, maxTmp에 저장되어있는 이전 행까지의 결과를 사용하여 minArr, maxArr에 현재 행까지의 계산 결과를 저장한다. 

- 다음 행으로 넘어가기 전에 minArr, maxArr에 존재하는 값들을 minTmp, maxTmp에 동일하게 넣어준다. (다음 행에서 현재 행까지의 결과를 사용할 수  있도록!)

- n번 반복이 끝나면 max_element와 min_element로 maxArr 배열의 최댓값과 minArr 배열의 최솟값을 출력했다.

---

[소스코드]

	/*
	BOJ 2096번: 내려가기
	DATE: 2022-01-17
	*/
	#include <iostream>
	#include <algorithm>
	using namespace std;
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, num;
	cin >> n;
	int minArr[3], maxArr[3], minTmp[3], maxTmp[3];
	int input[3];
	for(int i = 0 ; i < n ; i++){
	cin >> input[0] >> input[1] >> input[2];
	if(i == 0) {
	for(int j = 0 ; j < 3 ; j++) minTmp[j] = maxTmp[j] = minArr[j] = maxArr[j] = input[j];
	continue;
	}
	minArr[0] = input[0] + min(minTmp[0], minTmp[1]);
	maxArr[0] = input[0] + max(maxTmp[0], maxTmp[1]);
	minArr[1] = input[1] + min({minTmp[0], minTmp[1], minTmp[2]});
	maxArr[1] = input[1] + max({maxTmp[0], maxTmp[1], maxTmp[2]});
	minArr[2] = input[2] + min(minTmp[1], minTmp[2]);
	maxArr[2] = input[2] + max(maxTmp[1], maxTmp[2]);
	for(int j = 0 ; j < 3 ; j++){
	minTmp[j] = minArr[j];
	maxTmp[j] = maxArr[j];
	}
	}
	cout << *max_element(maxArr, maxArr + 3) << " " << *min_element(minArr, minArr + 3);
	return 0;
	}

view raw 2096.cpp hosted with ❤ by GitHub

---

2022-01-17

Gold 4

- 다이나믹 프로그래밍

- 슬라이딩 윈도우