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

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

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 현재 위치에서 도달할 수 있는 경우에 대해서 생각하고 이를 DP로 해결

 

2. 최솟값과 최댓값을 동시에 구하기

2-1. 왼쪽 : 상단 왼쪽과 상단 중앙

dp[n][left] = min(dp[n-1][left], dp[n-1][mid]) + num[n][left]

2-2. 중앙 : 상단 3개 모두 다

dp[n][mid] = min(dp[n-1][left], dp[n-1][mid], dp[n-1][right]) + num[n][mid]

2-3. 오른쪽 : 상단 오른쪽과 상단 중앙

dp[n][right] = min(dp[n-1][mid], dp[n-1][right]) + num[n][right]

 

3. 마지막 층의 3칸 중 최댓값과 최솟값을 순서대로 출력

 

과정

예제 1번으로 최댓값을 구하는 과정을 자세히 알아보겠습니다.

 

첫 번째 층은 이전 층이 없으므로 현재 칸의 점수를 그대로 입력합니다.

 

 

두 번째 층부터는 이전 층이 존재하므로, 정상적으로 검사를 합니다.

왼쪽 칸은 이전 층의 왼쪽과 중앙으로부터 영향을 받습니다.

그래서, 두 수 중 큰 수를 찾아서 현재 칸의 점수를 더합니다.

이전 층의 중앙값(2)이 더 크므로 여기에서 현재 칸의 점수(4)를 더합니다.

 

중앙 칸은 이전 층의 모든 칸으로부터 영향을 받습니다.

그래서, 세 수 중 큰 수를 찾아서 현재 칸의 점수를 더합니다.

 

이전 층의 오른쪽 칸의 값(3)이 더 크므로 여기에서 현재 칸의 점수(5)를 더합니다.

 

 

오른쪽 칸은 이전 층의 중앙과 오른쪽 칸으로부터 영향을 받습니다.

그래서, 두 수 중 큰 수를 찾아서 현재 칸의 점수를 더합니다.

이전 층의 오른쪽 칸의 값(3)이 더 크므로 여기에서 현재 칸의 점수(6)를 더합니다.

 

위 방식으로 다음 층까지 진행하면, 예제 1번의 최댓값인 18을 얻을 수 있습니다.

최솟값도 위 방식과 유사합니다.

매 단계별로 두 수 또는 세 수 중에서 최솟값을 찾아서 현재 칸의 점수를 더하면 됩니다.

 

추가

위 문제의 메모리 제한은 4MB입니다.

그래서, 모든 층에 대한 데이터를 저장할 경우 100'000(층) * 3(칸) * 4(int) * 3(각 칸 점수, 최댓값 저장, 최솟값 저장) = 3'600'000byte로 약 3.6MB입니다.

 

메모리 공간을 절약하고 싶다면, 최댓값과 최솟값 저장 배열을 이전 층과 현재 층에 대해서만 저장하도록 합니다.

 

 

---

03. 정답 코드

// 골드 5 - 2096번 : 내려가기
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MIN = 0;
const int MAX = 1;

const int LEFT = 0;
const int MID = 1;
const int RIGHT = 2;

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> input(3, 0);
    vector<vector<int>> result(2, vector<int>(3, 0));
    vector<vector<int>> temp(2, vector<int>(3, 0));

    // 첫 줄 입력
    cin >> result[MIN][LEFT] >> result[MIN][MID] >> result[MIN][RIGHT];
    result[MAX][LEFT] = result[MIN][LEFT];
    result[MAX][MID] = result[MIN][MID];
    result[MAX][RIGHT] = result[MIN][RIGHT];

    // 한 줄씩 입력
    for(int i = 1; i < N; i++)
    {
        cin >> input[LEFT] >> input[MID] >> input[RIGHT];
        
        // 깊은 복사
        temp = result;

        // 왼쪽
        result[MIN][LEFT] = min(temp[MIN][LEFT] + input[LEFT], temp[MIN][MID] + input[LEFT]);
        result[MAX][LEFT] = max(temp[MAX][LEFT] + input[LEFT], temp[MAX][MID] + input[LEFT]);

        // 중앙
        result[MIN][MID] = min(min(temp[MIN][LEFT] + input[MID], temp[MIN][MID] + input[MID]), temp[MIN][RIGHT] + input[MID]);
        result[MAX][MID] = max(max(temp[MAX][LEFT] + input[MID], temp[MAX][MID] + input[MID]), temp[MAX][RIGHT] + input[MID]);

        // 오른쪽
        result[MIN][RIGHT] = min(temp[MIN][MID] + input[RIGHT], temp[MIN][RIGHT] + input[RIGHT]);
        result[MAX][RIGHT] = max(temp[MAX][MID] + input[RIGHT], temp[MAX][RIGHT] + input[RIGHT]);
    }

    // 최소 최대 찾기
    int min_result = min(min(result[MIN][LEFT], result[MIN][MID]), result[MIN][RIGHT]);
    int max_result = max(max(result[MAX][LEFT], result[MAX][MID]), result[MAX][RIGHT]);

    // 결과
    cout << max_result << " " << min_result << "\n";
}

 

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!