[BOJ 2096 // C++] 내려가기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2096번 문제인 내려가기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2096

2096번: 내려가기

이 문제는 단순한 DP문제이다. 단, 메모리제한이 4MB이므로 모든 input을 한번에 받고 계산해나가는 것은 이 문제에서는 불가능하다.

따라서, 이미 이전에 사용하고 필요없어진 값은 저장하지 않는 방식으로 다음과 같이 구현했다.

 

0) 1번째 줄만 읽었을 때, 1, 2, 3열의 수로 각각 끝나는 최솟값과 최솟값은 둘 다 각 열에 들어온 숫자와 같다.

이 값으로 배열을 초기화한다.

1) i(>=1)번째 줄까지의 1, 2, 3열의 수로 각각 끝날 최솟값과 최댓값을 저장할 배열이 있을 때, 값 3개를 읽어와 i+1번째 줄까지의 1, 2, 3열의 수로 각각 끝날 최솟값과 최댓값을 갱신한다. 이를 N번째 줄까지의 결과를 얻을 때까지 반복한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::cin;
using std::cout;
using std::min;
using std::max;

int nums[3][2]; //두번째 성분이 0이면 이 칸으로 도착하는 최솟값, 1이면 최댓값을 저장해나간다

int main()
{
    int N; cin >> N;
    int x, y, z; cin >> x >> y >> z;
    nums[0][0] = x, nums[0][1] = x;
    nums[1][0] = y, nums[1][1] = y;
    nums[2][0] = z, nums[2][1] = z;

    for (int i = 1;i < N;i++) {
        int a, b, c; cin >> a >> b >> c;
        int temp00 = min(nums[0][0], nums[1][0]) + a;
        int temp01 = max(nums[0][1], nums[1][1]) + a;
        int temp10 = min(nums[0][0], min(nums[1][0], nums[2][0])) + b;
        int temp11 = max(nums[0][1], max(nums[1][1], nums[2][1])) + b;
        int temp20 = min(nums[1][0], nums[2][0]) + c;
        int temp21 = max(nums[1][1], nums[2][1]) + c;
        nums[0][0] = temp00; nums[0][1] = temp01;
        nums[1][0] = temp10; nums[1][1] = temp11;
        nums[2][0] = temp20; nums[2][1] = temp21;
    }
    cout << max(nums[0][1], max(nums[1][1], nums[2][1])) << ' ' << min(nums[0][0], min(nums[1][0], nums[2][0]));
}