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

 

#include <iostream>
#include <algorithm>

using namespace std;

int DP[100001][3];

int main(void)
{
	int n=0;
	
	cin>>n;
	
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<3; j++)
		{
			cin>>DP[i][j];
		}
	}
	
	int max1[3]={DP[0][0],DP[0][1],DP[0][2]};
	int max2[3]={0};
	int min1[3]={DP[0][0],DP[0][1],DP[0][2]};
	int min2[3]={0};
	
	for(int i=1; i<n; i++)
	{
		for(int j=0; j<3; j++)
		{
			int max=0;
			if(max<max1[j-1]+DP[i][j]&&j-1>-1)
			{
				max=max1[j-1]+DP[i][j];
			}
			if(max<max1[j]+DP[i][j])
			{
				max=max1[j]+DP[i][j];	
			}
			if(max<max1[j+1]+DP[i][j]&&j+1<3)
			{
				max=max1[j+1]+DP[i][j];
			}
			max2[j]=max;
			
			int min=987654321;
			if(min>min1[j-1]+DP[i][j]&&j-1>-1)
			{
				min=min1[j-1]+DP[i][j];
			}
			if(min>min1[j]+DP[i][j])
			{
					min=min1[j]+DP[i][j];
			}
			if(min>min1[j+1]+DP[i][j]&&j+1<3)
			{
					min=min1[j+1]+DP[i][j];
			}
			min2[j]=min;
		}
		for(int j=0; j<3; j++)
		{
			max1[j]=max2[j];
		}
		for(int j=0; j<3; j++)
		{
			min1[j]=min2[j];
		}
	}
	
	cout<<max({max1[0], max1[1], max1[2]})<<" ";
	cout<<min({min1[0], min1[1], min1[2]})<<" ";
	
	return 0;
}

 

별이 내려가면서 얻을 수 있는 최댓값과 최솟값을 출력하는 문제이다.

별은 자기 index에서 가로로 +-1위치까지는 이동이 가능하다.

 

최댓값과 최솟값을 어떻게 구하면 좋을까??

내려가면서 각 층마다 점수를 갱신해 준다??

최댓값

2층에 값을 경신하는 순서를 간단하게 그려보았다.(최댓값)

(1,0)=max(1+4, 2+4) , (1,1)=max(1+5, 2+5, 3+5), (1,2)=max(2+6, 3+6)

이러한 순서로 마지막 층까지 계산해 주면 최댓값을 구할 수 있다.

최솟값

 

최솟값도 위와 같은 순서로 계산해 주면 된다.

 

이 문제에서 중요한 부분은

메모리 제한이다.

 

메모리가 4MB 정도로 제한되어 있어서 배열을 선언할 때 int DP[100001][3]; 이렇게 하나만 선언할 수 있다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int DP[100001][3];
int DP2[100001][3];
int arr[100001][3];

int main(void)
{
	int n=0;
	
	cin>>n;
	
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<3; j++)
		{
			cin>>arr[i][j];
		}
	}
	
	DP[0][0]=arr[0][0];
	DP[0][1]=arr[0][1];
	DP[0][2]=arr[0][2];
	
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<3; j++)
		{
			if(DP[i+1][j-1]<DP[i][j]+arr[i+1][j-1]&&j-1>-1)
			{
				DP[i+1][j-1]=DP[i][j]+arr[i+1][j-1];
			}
			if(DP[i+1][j]<DP[i][j]+arr[i+1][j])
			{
				DP[i+1][j]=DP[i][j]+arr[i+1][j];
			}
			if(DP[i+1][j+1]<DP[i][j]+arr[i+1][j+1]&&j+1<3)
			{
				DP[i+1][j+1]=DP[i][j]+arr[i+1][j+1];
			}
		}
	}
	
	cout<<max({DP[n-1][0], DP[n-1][1], DP[n-1][2]})<<" ";
	
	
	DP2[0][0]=arr[0][0];
	DP2[0][1]=arr[0][1];
	DP2[0][2]=arr[0][2];
	
	for(int i=1; i<n; i++)
	{
		for(int j=0; j<3; j++)
		{
			DP2[i][j]=987654321;
		}
	}
	
	
	
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<3; j++)
		{
			if(DP2[i+1][j-1]>DP2[i][j]+arr[i+1][j-1]&&j-1>-1)
			{
				DP2[i+1][j-1]=DP2[i][j]+arr[i+1][j-1];
			}
			if(DP2[i+1][j]>DP2[i][j]+arr[i+1][j])
			{
				DP2[i+1][j]=DP2[i][j]+arr[i+1][j];
			}
			if(DP2[i+1][j+1]>DP2[i][j]+arr[i+1][j+1]&&j+1<3)
			{
				DP2[i+1][j+1]=DP2[i][j]+arr[i+1][j+1];
			}
		}
	}
	
	cout<<min({DP2[n-1][0], DP2[n-1][1], DP2[n-1][2]});
	
	
	
	return 0;
}

내가 처음에 제출한 코드이다. 바로 메모리 초과가 발생해 버렸다.

 

이 문제는 이전층에 대한 정보만 가지고 있으면 해결되기 때문에 많은 공간을 필요로 하지 않는다.

이전층에 대한 정보만 잘 저장하자.(최솟값, 최댓값 따로)

int max1[3]={DP[0][0],DP[0][1],DP[0][2]};
int max2[3]={0};
int min1[3]={DP[0][0],DP[0][1],DP[0][2]};
int min2[3]={0};