[백준 2096번] 내려가기

문제 설명

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

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

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

입력

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

출력

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

접근 방식 및 풀이

최대 점수와 최소 점수 두가지를 구해야 하지만 일단 최대 점수를 구하는 방법에 대해서 설명하겠다.

첫번째 줄부터 마지막 줄까지 한 줄씩 계산하며 내려간다. 현재 어느 특정 줄에 있다고 가정해보자. 윗줄부터 내려왔기 때문에 바로 이전 줄까지 오면서의 최대 점수를 우리는 이미 구했을 것이다. 또한 한 줄이 왼쪽, 중간, 오른쪽 총 3칸으로 이루어져 있기 때문에 각 칸마다 최대 점수를 구했을 것이다. 당연하지만 현재 줄도 3칸으로 이루어져 있다. 3칸이 최대 점수를 계산하는 방법이 다르기 때문에 각 칸 별로 설명해보겠다.

왼쪽 칸

왼쪽 칸의 경우, 이전 줄의 왼쪽 칸과 중간 칸에서만 올 수 있다. 오른쪽 칸에서는 떨어져 있기 때문이다. 따라서 이전 줄의 왼쪽 칸과 중간 칸까지 가는 최대 점수 중 높은 숫자를 선택해서 현재 칸의 점수를 더한다. 그렇게 해서 나온 값이 현재 칸까지 오는 최대 점수가 된다.

중간 칸

중간 칸의 경우, 이전 줄의 어느 칸에서도 올 수 있다. 따라서 이전 줄의 왼쪽 칸, 중간 칸, 오른쪽 칸까지 가는 최대 점수 중 가장 높은 숫자를 선택해서 현재 칸의 점수를 더한다. 그렇게 해서 나온 값이 현재 칸까지 오는 최대 점수가 된다.

오른쪽 칸

오른쪽 칸의 경우, 이전 줄의 오른쪽 칸과 중간 칸에서만 올 수 있다. 왼쪽 칸에서는 떨어져 있기 때문이다. 따라서 이전 줄의 오른쪽 칸과 중간 칸까지 가는 최대 점수 중 높은 숫자를 선택해서 현재 칸의 점수를 더한다. 그렇게 해서 나온 값이 현재 칸까지 오는 최대 점수가 된다.

이렇게 하면 한 줄 계산이 끝난다. 해당 과정을 맨 마지막 줄까지 반복하면 마지막 줄의 왼쪽, 중간, 오른쪽 칸까지 가는 3개의 최대 점수가 나온다. 3개를 비교하여 가장 높은 점수가 최종 최대 점수가 된다.

최소 점수의 경우, 위와 동일한 과정을 통해서 구하되 높은 숫자를 선택하는 것이 아니라 낮은 숫자를 선택한다.

코드

문제 풀이에 사용한 언어: C

#include <stdio.h>

int min2(int num1, int num2);
int min3(int num1, int num2, int num3);
int max2(int num1, int num2);
int max3(int num1, int num2, int num3);

int main(){
    int num;
    scanf("%d\n", &num);
    
    int array[3];
    int max[3] = {0, 0, 0};
    int curMax[3];
    int min[3] = {0, 0, 0};
    int curMin[3];
    
    for(int i = 0; i < num; i++){ // 첫번째 줄부터 마지막 줄까지 반복
        scanf("\n%d %d %d\n", &array[0], &array[1], &array[2]);
        
        curMax[0] = max2(max[0] + array[0], max[1] + array[0]); // 왼쪽 칸으로는 이전 단계의 중간 칸과 왼쪽 칸에서 올 수 있으므로 두 개 중 높은 숫자를 선택한다.
        curMax[2] = max2(max[1] + array[2], max[2] + array[2]); // 오른쪽 칸으로는 이전 단계의 중간 칸과 오른쪽 칸에서 올 수 있으므로 두 개 중 높은 숫자를 선택한다.
        curMax[1] = max3(max[0] + array[1], max[1] + array[1], max[2] + array[1]); // 중간 칸으로는 이전 단계의 어느 칸에서도 올 수 있으므로 세 개 중 높은 숫자를 선택한다.
        
        for(int j = 0; j < 3; j++){
            max[j] = curMax[j]; // 최대 점수 업데이트
        }
        
        curMin[0] = min2(min[0] + array[0], min[1] + array[0]); // 왼쪽 칸으로는 이전 단계의 중간 칸과 왼쪽 칸에서 올 수 있으므로 두 개 중 낮은 숫자를 선택한다.
        curMin[2] = min2(min[1] + array[2], min[2] + array[2]); // 오른쪽 칸으로는 이전 단계의 중간 칸과 오른쪽 칸에서 올 수 있으므로 두 개 중 낮은 숫자를 선택한다.
        curMin[1] = min3(min[0] + array[1], min[1] + array[1], min[2] + array[1]); // 중간 칸으로는 이전 단계의 어느 칸에서도 올 수 있으므로 세 개 중 낮은 숫자를 선택한다.
        
        for(int j = 0; j < 3; j++){
            min[j] = curMin[j]; // 최소 점수 업데이트
        }
    }
    
    int resultMax = max3(max[0], max[1], max[2]); // 마지막 줄까지 왔을 때 최대 점수
    int resultMin = min3(min[0], min[1], min[2]); // 마지막 줄까지 왔을 때 최소 점수
    
    printf("%d %d\n", resultMax, resultMin);
    
    return 0;
}

// 두개의 수 중에 작은 수
int min2(int num1, int num2){
    return num1 < num2 ? num1 : num2;
}

// 세개의 수 중에 작은 수
int min3(int num1, int num2, int num3){
    if(num1 <= num2 && num1 <= num3){
        return num1;
    }
    else if(num2 <= num1 && num2 <= num3){
        return num2;
    }
    return num3;
}

// 두개의 수 중에 큰 수
int max2(int num1, int num2){
    return num1 > num2 ? num1 : num2;
}

// 세개의 수 중에 큰 수
int max3(int num1, int num2, int num3){
    if(num1 >= num2 && num1 >= num3){
        return num1;
    }
    else if(num2 >= num1 && num2 >= num3){
        return num2;
    }
    return num3;
}