[백준] 2096번 : 내려가기 [C/C++]

#문제

2096번: 내려가기

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

2096번: 내려가기

 

---

#접근방법

이 문제는 접근방법은 쉬우나, 메모리 제한이 4MB밖에 안된다. 따라서 메모리 초과가 걸리지 않도록 배열의 수를 줄이는 방법을 생각해야한다.

반응형

---

#풀이

#메모리 초과가 걸리는 풀이

#include <stdio.h>
#define max(x,y) (x > y ? x : y)
#define min(x,y) (x < y ? x : y)

int arr[100005][3];
int max_arr[100005][3];
int min_arr[100005][3];

int main(){
	int n;
	int x,y,z;
	int ans1,ans2;
	
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)
		for(int j=0;j<3;j++)
			scanf("%d",&arr[i][j]);
	
	for(int i=1;i<=n;i++){
		max_arr[i][0] = max(max_arr[i-1][0],max_arr[i-1][1]) + arr[i][0];
		max_arr[i][1] = max(max(max_arr[i-1][0],max_arr[i-1][1]),max_arr[i-1][2]) + arr[i][1];
		max_arr[i][2] = max(max_arr[i-1][1],max_arr[i-1][2]) + arr[i][2];
		
		min_arr[i][0] = min(min_arr[i-1][0],min_arr[i-1][1]) + arr[i][0];
		min_arr[i][1] = min(min(min_arr[i-1][0],min_arr[i-1][1]),min_arr[i-1][2]) + arr[i][1];
		min_arr[i][2] = min(min_arr[i-1][1],min_arr[i-1][2]) + arr[i][2];
	}
	
	ans1 = max(max(max_arr[n][0],max_arr[n][1]),max_arr[n][2]);
	ans2 = min(min(min_arr[n][0],min_arr[n][1]),min_arr[n][2]);
	
	printf("%d %d",ans1,ans2);
	
	return 0;
}

 

#정답 풀이

#include <stdio.h>
#define max(x,y) (x > y ? x : y)
#define min(x,y) (x < y ? x : y)

int max_arr[2][3];
int min_arr[2][3];

int main(){
	int n;
	int x,y,z;
	int	k = 0;
	int ans1,ans2;
	
	scanf("%d",&n);
	
	for(int i=0;i<n;i++){		
		scanf("%d %d %d",&x,&y,&z);
		
		max_arr[k][0] = max(max_arr[1-k][0],max_arr[1-k][1]) + x;
		max_arr[k][1] = max(max(max_arr[1-k][0],max_arr[1-k][1]),max_arr[1-k][2]) + y;
		max_arr[k][2] = max(max_arr[1-k][1],max_arr[1-k][2]) + z;
		
		min_arr[k][0] = min(min_arr[1-k][0],min_arr[1-k][1]) + x;
		min_arr[k][1] = min(min(min_arr[1-k][0],min_arr[1-k][1]),min_arr[1-k][2]) + y;
		min_arr[k][2] = min(min_arr[1-k][1],min_arr[1-k][2]) + z;
		
		k = 1 - k;
	}
	
	ans1 = max(max(max_arr[1-k][0],max_arr[1-k][1]),max_arr[1-k][2]);
	ans2 = min(min(min_arr[1-k][0],min_arr[1-k][1]),min_arr[1-k][2]);
	
	printf("%d %d",ans1,ans2);
	
	return 0;
}

 

메모리 초과가 걸리는 풀이와 메모리 초과가 걸리지 않은 풀이 2가지를 준비했다.

 

풀이는 같으나 배열의 크기가 100,000개와 2개로 다르다.

 

#풀이

메모리 초과가 걸리는 풀이를 보면서 먼저 설명하겠다.

 

arr[i][0]에 있는 값은 arr[i-1][0], arr[i-1][1]에 있는 값 중에 큰값, 또는 작은값을 선택하여 누적시키면 된다.

arr[i][2]도 arr[i][0]과 마찬가지로 arr[i-1][1], arr[i-1][2]에 있는 값 중에 선택하여 누적시키면된다.

arr[i][1]은 arr[i-1][0], arr[i-1][1], arr[i-1][2]에 있는 값 3개 중에서 선택하여 누적시키면 된다.

 

반복문을 돌리고 arr[n][0], arr[n][1], arr[n][2]에 있는 값 중에서 큰값, 또는 작은값을 고르면 정답이다.

 

하지만 이 방법을 쓰면 100,000개의 배열을 써야 하므로 메모리 초과가 걸리게 된다.

 

잘 생각해보면 i번 째 배열과 i-1번 째 배열만 사용하므로 배열 2개만 있으면 구할 수 있다.

 

0번과 1번을 번갈아 가면서 사용하면 배열 2개로 정답을 구할 수 있다.

 

초기값 0을 넣은 k라는 변수를 사용하여 반복문이 끝날 때 마다 k = 1 - k을 사용하여 0과 1를 번갈아 가도록 설계하였다.

 

그러면 배열 2개만 사용하여 풀 수 있으므로 메모리 초과가 걸리지 않고 문제를 풀 수 있다.

---

#성능

---

#정리

이전 값을 이용하는 다이나믹 프로그래밍 알고리즘을 사용하는 것,

 

현재 값, 이전 값 2개의 변수만 사용하여 풀 수 있다는 사실을 안다는 것,

 

배열 2개만 사용하여 구현을 할 수 있으면 풀 수 있는 문제였다.