c++ 백준_2096_"내려가기"

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

2096번: 내려가기

 

아래에서 위로 올라가며 살펴보았다.

​

제일 아래

현재 위치와 그 양쪽,

총 3칸을 살펴보며

해당 바로 위층(i-1)의 값과 더했을 때

최소, 최대가 되는 것을 DP 배열에 삽입하였다.

​

계산에 편리하기 위해

무조건 현재 위치, 현재에서 왼쪽위치, 현재에서 오른쪽 위치를

검사하였다.

그러면 한 행에 총 5칸이 필요하다.

​

최대값을 구할 때는 전역으로 DP를 뒀으니 자동으로 빈 칸은 0이 들어가 최대값을 구하는데 영향을 끼치지 않는다.

최소값을 구할 때는 DP칸 제일 왼쪽, 오른쪽(쓸모없는 칸)은 막연하게 큰 수를 집어넣어 최소값을 구하는데 영향을 끼치지 않게 하였다.

​

메모리 제한이 있어서

무지성으로 board판과 똑같은 DP판을 만들어 사용하니

메모리 초과가 떠서

DP는 2줄짜리 판을 만들어 사용하였다.

​

#include <iostream>
#include <vector>
using namespace std;

#define INF 1000000000
int board[100001][5];
int dp[2][5];


int find_max_score(int N) {

	int dp_idx = 1;
	for (int i = N; i >= 2; i--) {
		for (int j = 1; j <= 3; j++) {

			int sum = 
				max(board[i-1][j] + dp[(dp_idx)%2][j-1], max(board[i - 1][j] + dp[(dp_idx) % 2][j], board[i - 1][j] + dp[(dp_idx) % 2][j + 1]));
			dp[(dp_idx + 1)%2][j] = sum;
		}
		dp_idx++;
	}

	return max(dp[dp_idx%2][1], max(dp[dp_idx%2][2], dp[dp_idx%2][3]));
}

int find_min_score(int N) {
	
	dp[1][0] = INF; dp[0][0] = INF;
	dp[1][4] = INF; dp[0][4] = INF;

	int dp_idx = 1;
	for (int i = N; i >= 2; i--) {
		for (int j = 1; j <= 3; j++) {

			int sum =
				min(board[i - 1][j] + dp[(dp_idx) % 2][j - 1], min(board[i - 1][j] + dp[(dp_idx) % 2][j], board[i - 1][j] + dp[(dp_idx) % 2][j + 1]));
			dp[(dp_idx + 1) % 2][j] = sum;
		}
		dp_idx++;

	}

	return min(dp[dp_idx % 2][1], min(dp[dp_idx % 2][2], dp[dp_idx % 2][3]));
}

int main(void) {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	
	cin >> N;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 3; j++) {
			cin >> board[i][j];
		}
	}


	for (int i = 1; i <= 3; i++) {
		dp[1][i] = board[N][i];
	}


	cout << find_max_score(N) << " ";

	for (int i = 1; i <= 3; i++) {
		dp[1][i] = board[N][i];
	}


	cout << find_min_score(N);


}