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

<style> .revenue_unit_wrap{ display:none; } </style>

 

 

2096번: 내려가기

 

문제!

---

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

 

 

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

---

요약하면 제일 윗칸에서 아래로 내려갈텐데

1번에선 1,2 / 2번에선 1,2,3 / 3번에선 2,3 식으로 이동가능한 그런 게임!

 

선택
O	O

	선택
O	O	O

		선택
	O	O

 

이렇게 끝까지 내려갔을때의 최대점수와 최소점수를 출력하면 되는 문제!

 

 

 

 

예전같았으면 바로 탐색을 돌렸겠지만 

이동에 대한 규칙이있다? >>>> 동적계획법!

 

 

그중 저는 [줄위치][칸위치] = 점수!

int dp[100001][3]={0}

방식으로 먼저 도전해 보았습니다.

 

하지만

 

(메모리초과 코드)

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


int N;

int Map[100001][3] = { 0 }; // 줄,칸 = 최대 수합
int dp[100001][3] = { 0 }; // 줄,칸 = 최대 수합
int dpMin[100001][3] = { 0 }; // 줄,칸 = 최대 수합


int main() {
	cin >> N;


	for (int i = 1; i <= N; i++) {
		cin >> Map[i][0] >> Map[i][1] >> Map[i][2];
	}




	for (int i = 0; i < 3; i++) {
		dp[1][i] = Map[1][i];
		dpMin[1][i]= Map[1][i];
	}

	for (int i = 2; i <= N; i++) {

		dp[i][0] = max(dp[i-1][0]+ Map[i][0],dp[i - 1][1]+ Map[i][0]);

		dp[i][1] = max(dp[i-1][0] + Map[i][1], dp[i - 1][1] + Map[i][1]);
		dp[i][1] = max(dp[i][1], dp[i - 1][2] + Map[i][1]);

		dp[i][2] = max(dp[i - 1][1] + Map[i][2], dp[i - 1][2] + Map[i][2]);


		dpMin[i][0] = min(dpMin[i - 1][0] + Map[i][0], dpMin[i - 1][1] + Map[i][0]);

		dpMin[i][1] = min(dpMin[i - 1][0] + Map[i][1], dpMin[i - 1][1] + Map[i][1]);
		dpMin[i][1] = min(dpMin[i][1], dpMin[i - 1][2] + Map[i][1]);

		dpMin[i][2] = min(dpMin[i - 1][1] + Map[i][2], dpMin[i - 1][2] + Map[i][2]);
	}

	vector<int>list;

	for (int i = 0; i < 3; i++) {
		list.push_back(dp[N][i]);
		list.push_back(dpMin[N][i]);
	}


	sort(list.begin(), list.end());
	


	cout << list[list.size() - 1] << " " << list[0] << endl;

	return 0;
}

 

.... 방법은 틀린것 같진 않지만... 메모리 초과가 발생하네요

 

 

 

메모리 초과를 보고 다시 생각해보니 

 

 

현재 구하려는것

1. 종점에서의 최대점수

2. 종점에서의 최소점수

 

종점..!

 

 

 

 

dp[줄의위치][칸위치] 에서 줄의 위치를 세어 줄 필요가 없을거 같다는 생각을 하게되었습니다. 

중간 지점의 값이 필요없기에

계속해서 갱신해서 최종 답만 얻어내면 될 것 같네요!

 

그럼바로

 

 

코드!

---

먼저 선언부에 N, 점수칸, 최대 dp, 최소 dp를 선언해 줍시다.

int N;

int Map[3] = { 0 }; // 전체
int dp[3] = { 0 }; //칸 = 최대 수합
int dpMin[3] = { 0 }; // 칸 = 최소 수합

 

 

(중요) dp연산을 시작하기에 앞서 가장 초기값을 설정

cin >> dp[0] >> dp[1] >> dp[2];

	for (int i = 0; i < 3; i++) {
		dpMin[i] = dp[i];
	}

 

 

다음으로는 dp와 dpmin에 대해서 따로 연산해줍시다. 

for (int i = 1; i < N; i++) {
		cin >> Map[0] >> Map[1] >> Map[2];

		int temp0 = dp[0];
		int temp1 = dp[1];
		int temp2 = dp[2];


		dp[0] = max(temp0 + Map[0], temp1 + Map[0]);

		dp[1] = max(temp0 + Map[1], temp1 + Map[1]);
		dp[1] = max(dp[1], temp2 + Map[1]);

		dp[2] = max(temp1 + Map[2], temp2 + Map[2]);

		temp0 = dpMin[0];
		temp1 = dpMin[1];
		temp2 = dpMin[2];


		dpMin[0] = min(temp0 + Map[0], temp1 + Map[0]);

		dpMin[1] = min(temp0 + Map[1], temp1 + Map[1]);
		dpMin[1] = min(dpMin[1], temp2 + Map[1]);

		dpMin[2] = min(temp1 + Map[2], temp2 + Map[2]);
	}

먼저 각 temp에 저장을 해두고

 

dp[0]의 경우 

신 dp[0] = 구 dp[0]+ 0번  , 구 dp[1] + 0번 으로 최신화!

dp[0] = max(temp0 + Map[0], temp1 + Map[0]);

 

이부분에서 약간헤멨는데

dp[0]에는 0번째로 도착했을때를 찾아야하므로

1  >> 0번째

0 >> 0번째

 

이렇게 2가지를 생각해야합니다.

 

 

나머지도 똑같은 방식으로 찾아주었습니다!

 

 

이제 값들을 모아 최솟값과 최댓값을 출력 하면 끝!

vector<int>list;

	for (int i = 0; i < 3; i++) {
		list.push_back(dp[i]);
		list.push_back(dpMin[i]);
	}


	sort(list.begin(), list.end());
	


	cout << list[list.size() - 1] << " " << list[0] << endl;

 

 

이번 문제를 통해 배운 내용

1. 동적계획법의 메모리 활용방식

2. 다시한번, 구해야 하는 것에 집중하기

 

 

 

 

끝!

 

 

 

ALL

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


int N;

int Map[3] = { 0 }; // 전체
int dp[3] = { 0 }; //칸 = 최대 수합
int dpMin[3] = { 0 }; // 칸 = 최소 수합


int main() {
	cin >> N;


	cin >> dp[0] >> dp[1] >> dp[2];

	for (int i = 0; i < 3; i++) {
		dpMin[i] = dp[i];
	}


	for (int i = 1; i < N; i++) {
		cin >> Map[0] >> Map[1] >> Map[2];

		int temp0 = dp[0];
		int temp1 = dp[1];
		int temp2 = dp[2];


		dp[0] = max(temp0 + Map[0], temp1 + Map[0]);

		dp[1] = max(temp0 + Map[1], temp1 + Map[1]);
		dp[1] = max(dp[1], temp2 + Map[1]);

		dp[2] = max(temp1 + Map[2], temp2 + Map[2]);

		temp0 = dpMin[0];
		temp1 = dpMin[1];
		temp2 = dpMin[2];


		dpMin[0] = min(temp0 + Map[0], temp1 + Map[0]);

		dpMin[1] = min(temp0 + Map[1], temp1 + Map[1]);
		dpMin[1] = min(dpMin[1], temp2 + Map[1]);

		dpMin[2] = min(temp1 + Map[2], temp2 + Map[2]);
	}
	

	
	vector<int>list;

	for (int i = 0; i < 3; i++) {
		list.push_back(dp[i]);
		list.push_back(dpMin[i]);
	}


	sort(list.begin(), list.end());
	


	cout << list[list.size() - 1] << " " << list[0] << endl;

	return 0;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!