[백준 2096] 내려가기

 

DP문제 RGB거리와 상당히 유사한 문제이다.

 

배열의 n-1번째부터 0번째까지 반대 방향으로 진행하면서 최고합, 최소합을 메모이제이션 하면서 구하면된다.

n이 최대 100000이라 DP로 그냥 풀리긴 하지만 메모리 제한을 보니 슬라이딩윈도우 기법을 요구하는 듯하다.

 

슬라이딩 윈도우는 일정한 구간을 훑으며 진행하는 기법이다.

글로 표현하면 뭔가 있어 보이는데, 배열 크기를 1로 만들어서 이전 배열에서 연산한것을 갱신만 해주면 된다.

 

colMax, colMin 은 최대합, 최소합 배열이고

tempMax, tempMin 은 이전계단의 값이다.

colMax, colMin 배열에 tempMax, tempMin의 값을 연산을 통해 업데이트 시켜주면 된다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int colMin[] = new int[3];
        int colMax[] = new int[3];
        int tempMin[] = new int[3];
        int tempMax[] = new int[3];
        
        int n = sc.nextInt();
        for(int i=0; i<n; i++) {
            for(int j=0; j<3; j++) {
                tempMax[j] = sc.nextInt();
                tempMin[j] = tempMax[j];
                tempMax[j] += Math.max(colMax[1], j==1 ? Math.max(colMax[0], colMax[2]) : colMax[j]);
                tempMin[j] += Math.min(colMin[1], j==1 ? Math.min(colMin[0], colMin[2]) : colMin[j]);
            }
            for(int j=0; j<3; j++) {
                colMax[j] = tempMax[j];
                colMin[j] = tempMin[j];
            }
        }
        Arrays.sort(colMax);
        Arrays.sort(colMin);
        System.out.println(colMax[2] + " " + colMin[0]);
    }
}