2022-05-18 알고리즘 문제(백준 2096 내려가기)

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

2096번: 내려가기

---

 

1 초

4 MB (하단 참고)

24538

9225

7168

36.750%

문제

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

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

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

---

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

---

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

---

메모리 제한이 4MB여서 기존의 했던 방식대로 2차원 DP 테이블을 N개만큼 선언해서 풀면

메모리 초과가 난다.

 

이를 해결하기 위해서는 N번만큼 3개의 입력이 들어오면 DP테이블을 최소한만 써서

입력 한줄한줄씩 바로 계산을 해주면 메모리 초과를 피할 수 있다.

 

문제에서 최대,최소 점수를 요구하기 때문에, 

최대 , 최소 점수를 저장하고, 갱신하는 DP_max, DP_min을 3개의 배열로 다음과 같이 선언한다.

 

 

 

DP_max[0]

DP_max[1]

DP_max[2]

 

DP_MIN[0]

DP_MIN[2]

DP_MIN[2]

 

이제 문제를 보자. 

0번쨰 즉, 제일 왼쪽으로 오는 경로는 제일왼쪽에서 내려오거나 [0], 중간에서 내려오는 경우[1] 2가지가 있다.

 

1번째, 중앙으로 오는 경로는 모두 포함된다. (제일왼쪽에서 내려오거나, 중간에서 내려오거나, 오른쪽에서 내려오는 경우 모두)

 

2번쨰, 제일 오른쪽으로 오는 경로는 제일 오른쪽 [2]에서 내려오거나, 중간에서 내려오는 경우 2가지가 있다.

 

일단 첫번쨰의 경우에는 DP_max[0],DP_min[0]에는 입력으로 받은 값을 그대로 넣어준다. (1번쨰,2번쨰도 마찬가지)

 

그러면 현재 상태는 다음과 같다. (예시 케이스의 첫번쨰를 사용하겠다)

 

DP_MAX[0]           1	DP_MAX[1]           2	DP_MAX[2]           3
DP_MIN[0]            1	DP_MIN[1]            2	DP_MIN[2]            3

이제, 다시 한줄씩 입력받는다.

4와 5, 6을 입력받고 DP_MAX[0]에는 제일 왼쪽으로 오는 경로 (왼쪽에서 내려오거나, 중앙에서 내려오거나)

의 최대값을 저장하고,

DP_MAX[1]에는 중간으로 오는 경로(왼쪽으로 내려오거나, 중앙에서 내려오거나, 오른쪽에서 내려오거나)

의 최대값을 마찬가지로 저장한다.

DP_MAX[2]에는 오른쪽으로 오는 경로(중앙에서 내려오거나, 오른쪽에서 내려오거나)

의 최대값을 또 저장한다.

 

DP_MIN은 최대값을 -> 최소값으로 바꾸고 실행하면 되는데,

 

DP_MIN[0]에는 제일 왼쪽으로 오는 경로 (왼쪽에서 내려오거나, 중앙에서 내려오거나)

의 최소값을 저장하고,

DP_MIN[1]에는 중간으로 오는 경로(왼쪽으로 내려오거나, 중앙에서 내려오거나, 오른쪽에서 내려오거나)

의 최소값을 마찬가지로 저장한다.

DP_MIN[2]에는 오른쪽으로 오는 경로(중앙에서 내려오거나, 오른쪽에서 내려오거나)

의 최소값을 또 저장한다.

 

이런식으로 로직을 구성하면 다음과 같이 표현할 수 있다.

for(int i = 0;i<n;i++){
			cin >> first >> second >> third;
				if(i == 0){
					dp_max[0] = first;
					dp_max[1] = second;
					dp_max[2] = third;
					dp_min[0] = first;
					dp_min[1] = second;
					dp_min[2] = third;
				}
				else{
					dp_max[0] = max(dp[0] + first,dp[1] + first) //제일 왼쪽
					dp_max[1] = max(max(dp[0]+second,dp[1]+second),dp[2]+second);//중간
					dp_max[2] = max(dp[2]+third,dp[1]+third); //제일 오른쪽
				}
		}

최대값만 적긴했는데 , 최소값도 똑같은 논리이다.

 

이때 또 주의해야 할 점이 있다면, 바로 직전의 DP값 (예를 들어서 i가 2라면 i가 1일때의 DP값)을 변수에 저장하고,

그 변수를 써야 한다.

왜냐하면 DP테이블을 갱신한다면 dp_max[1]은 dp[0] + second일 떄 dp[0]이 i가 1일때의 DP값이 아니라,

i가 2일떄의 DP값이 되기 떄문에 i-1번째 DP 테이블을 저장해놓고 코드를 쓰는 것이 좋다.

 

#include <iostream>

//백준 2096 
/*기존의 하던 방식대로 2차원 dp테이블선언시 메모리 초과 -> n번만큼 갱신하면서 최대,최소 저장
*/

using namespace std;
int max(int a,int b){
    if(a>b){
        return a;
    }
    else{
        return b;
    }
}
 
int min(int a,int b){
    if(a<b){
        return a;
    }
    else{
        return b;
    }
}
int main(void){
    int arr[3]; //한 라인에 3개씩 입력받으면서
    int dp[3]; //max값을 갱신
    int mdp[3]; //min값 갱신
    int n;
    cin >> n;
    for(int i = 0;i<n;i++){
        cin >> arr[0] >> arr[1] >> arr[2];
        int temp_one = dp[0]; //i-1번째 max dp저장
        int temp_two = dp[1];
        int temp_three = dp[2];
 
        int mdp_one = mdp[0]; //i-1번쨰 min dp 저장
        int mdp_two = mdp[1];
        int mdp_three = mdp[2];
 
        if(i == 0){ //i가 0일떄는 dp값이 입력받은 값 그대로
            dp[0] = arr[0];
            dp[1] = arr[1];
            dp[2] = arr[2];
            mdp[0] = arr[0];
            mdp[1] = arr[1];
            mdp[2] = arr[2];
 
        }
        else{ //i가 0이 아닐떄 0,1,2번째에 대해서 갱신
            dp[0] = max(dp[0] + arr[0],dp[1] + arr[0]);
            int big = max(temp_one+arr[1],temp_three+arr[1]);
            dp[1] = max(big,temp_two + arr[1]);
            dp[2] = max(temp_two + arr[2],temp_three + arr[2]);
 
            mdp[0] = min(mdp_one + arr[0],mdp_two + arr[0]);
            int small = min(mdp_one+arr[1],mdp_two+arr[1]);
            mdp[1] = min(small,mdp_three + arr[1]);
            mdp[2] = min(mdp_two + arr[2], mdp_three + arr[2]);
        }

    }
 
    cout << max(max(dp[0],dp[1]),dp[2]) << ' '; 
    cout << min(min(mdp[0],mdp[1]),mdp[2]);
 
}