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

www.acmicpc.net/problem/2096

2096번: 내려가기

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍
• 슬라이딩 윈도우

 

---

 

⊙ 문제 접근 과정

 

그렇게 어렵지는 않은 문제다. 공간 복잡도를 조금만 신경 쓴다면.

메모리 제한이 4MB이기에 공간을 잘 사용해야 한다.

 

변수를 여러 개 설정해주고 매번 갱신해 공간을 절약하는 방법을 선택했다.

 

아래 예시를 통해 접근 과정을 알아보자.

3

1 2 3

4 5 6

7 8 9

 

N=3, 3줄을 입력받는다.

첫 번째 줄은 1 2 3,  값이 하나이므로 최댓값과 최솟값은 동일!

변수에 최댓값과 최솟값을 저장해준다.

 

2번째 줄부터 반복문을 돌리고 값을 갱신해준다.

4에는 1, 2가 올 수 있다. 2번째 줄 1번째 값의 최댓값은 6, 최솟값은 5

5에는 1, 2, 3 전부 올 수 있다. 2번째 줄 2번째 값의 최댓값은 8, 최솟값은 6

6에는 2, 3이 올 수 있다. 2번째 줄 3번째 값의 최댓값은 9, 최솟값은 7

 

이런 식으로 반복한다. 최댓값과 최솟값에 대해 따로 변수로 지정하여.

최종적으로 저장된 DP 배열의 값을 출력하면 된다.

 

정답 코드에도 이해를 돕기 위해 주석을 달아놨다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N; //줄 개수
    scanf("%d",&N);
    int Max[3],Min[3],input[6], result_MAX,result_MIN;
    scanf("%d %d %d", &Max[0], &Max[1], &Max[2]); //첫번째 줄 값

    Min[0]=Max[0];
    Min[1]=Max[1];
    Min[2]=Max[2]; //첫번째 값이라서 mix, min 다 넣어줌

    for(int i=1; i<N;i++) { //두번째줄부터 for문
        scanf("%d %d %d", &input[0], &input[1], &input[2]);
        input[3]=input[0];
        input[4]=input[1];
        input[5]=input[2]; // 0,1,2는 MAX, 3,4,5는 MIN

        input[0] += max(Max[0],Max[1]);
        input[1] += max(max(Max[0],Max[1]), Max[2]);
        input[2] += max(Max[1],Max[2]);
        Max[0] = input[0];
        Max[1] = input[1];
        Max[2] = input[2]; //새로운 줄 갱신 (최대)

        input[3] += min(Min[0],Min[1]);
        input[4] += min(min(Min[0],Min[1]), Min[2]);
        input[5] += min(Min[1],Min[2]);
        Min[0] = input[3];
        Min[1] = input[4];
        Min[2] = input[5]; //새로운 줄 갱신 (최소)
    }

    result_MAX = max(max(Max[0],Max[1]),Max[2]);
    result_MIN = min(min(Min[0],Min[1]),Min[2]);

    printf("%d %d", result_MAX, result_MIN);
}

 

---

⊙ 결과

 

 

---

 

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!