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

 

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

 

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

2096번: 내려가기

---

 

해결전략

 

동적계획법 Dynamic Programming, DP

슬라이딩 윈도우 알고리즘 Sliding Window Algorithm

 

---

 

처음 시도한 코드 - 메모리 초과

 

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

int n;
vector<vector<int>> v;
vector<vector<int>> dp, dpMax;
int minValue = 2147000000, maxValue = 0;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n, vector<int>(3));
	dp.resize(n, vector<int>(3));
	dpMax.resize(n, vector<int>(3));
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < 3; x++) {
			cin >> v[y][x];

			if (y == n - 1) {
				dp[y][x] = v[y][x];
				dpMax[y][x] = v[y][x];
			}
		}
	}

	if (n == 1) {
		cout << max(v[0][0], max(v[0][1], v[0][2])) << " " << min(v[0][0], min(v[0][1], v[0][2]));
		return 0;
	}

	for (int y = n - 2; y >= 0; y--) {
		for (int x = 0; x < 3; x++) 
		{	
			if (0 <= x - 1 && x + 1 < 3){
				dp[y][x] = v[y][x] + min(dp[y + 1][x - 1], min(dp[y + 1][x], dp[y+1][x + 1]));
				dpMax[y][x] = v[y][x] + max(dpMax[y + 1][x - 1], max(dpMax[y + 1][x], dpMax[y + 1][x + 1]));
			}
			else if (0 <= x - 1 && x + 1 >= 3){
				dp[y][x] = v[y][x] + min(dp[y + 1][x - 1], dp[y + 1][x]);
				dpMax[y][x] = v[y][x] + max(dpMax[y + 1][x - 1], dpMax[y + 1][x]);
			}
			else if (0 > x - 1 && x + 1 < 3){
				dp[y][x] = v[y][x] + min(dp[y + 1][x], dp[y + 1][x + 1]);
				dpMax[y][x] = v[y][x] + max(dpMax[y + 1][x], dpMax[y + 1][x + 1]);
			}

			if (y == 0) {
				minValue = min(minValue, dp[y][x]);
				maxValue = max(maxValue, dpMax[y][x]);
			}
		}
	}

	cout << maxValue << " " << minValue;

	return 0;
}

 

 

메모리 계산 시 유의사항

C++ 자체에서 메모리를 1~2MB정도 사용한다. 

iostream 사용시 기본 2MB, 미사용시 기본 1MB 정도 사용

---

 

 

정답 코드

 

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

// 전역 변수 선언
int n; // 입력 받을 숫자의 개수
vector<int> v(3); 							// 각 행의 입력 값 3개를 저장할 벡터
vector<int> dp(3), next_dp(3); 				// 현재 상태와 다음 상태를 저장할 벡터, 최소값 계산용
vector<int> dpMax(3), next_dpMax(3); 		// 현재 상태와 다음 상태를 저장할 벡터, 최대값 계산용
int minValue = 2147000000, maxValue = 0; 	// 계산될 최소값과 최대값을 저장할 변수

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n; 
    for (int y = 0; y < n; y++) { 
        for (int x = 0; x < 3; x++) { 
            cin >> v[x];
        }

        if (y == 0) { // 첫 번째 행일 경우
            dp = v; // dp 벡터를 입력 값으로 초기화
            dpMax = v; // dpMax 벡터도 입력 값으로 초기화
            continue; // 첫 번째 행이므로 계산 없이 다음 반복으로 넘어감
        }

        // 다음 단계의 최소값 계산
        next_dp[0] = v[0] + min(dp[0], dp[1]);
        next_dp[1] = v[1] + min({ dp[0], dp[1], dp[2] });
        next_dp[2] = v[2] + min(dp[1], dp[2]);
        // 다음 단계의 최대값 계산
        next_dpMax[0] = v[0] + max(dpMax[0], dpMax[1]);
        next_dpMax[1] = v[1] + max({ dpMax[0], dpMax[1], dpMax[2] });
        next_dpMax[2] = v[2] + max(dpMax[1], dpMax[2]);

        dp = next_dp; // 계산된 다음 단계의 최소값을 현재 상태로 업데이트
        dpMax = next_dpMax; // 계산된 다음 단계의 최대값을 현재 상태로 업데이트
    }

    // 전체 행에 대한 최소값과 최대값 찾기
    minValue = *min_element(dp.begin(), dp.end()); // dp 벡터에서 최소값 찾기
    maxValue = *max_element(dpMax.begin(), dpMax.end()); // dpMax 벡터에서 최대값 찾기

    cout << maxValue << " " << minValue; // 최대값과 최소값 출력

    return 0; // 프로그램 종료
}

 

 

 

 

---