이번에 풀어본 문제는
백준 2096번 내려가기 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        int [] max = new int[3];
        int [] min = new int[3];
        int [] map = new int[3];
        int [] tmp = new int[3];

        //첫줄 초기화
        StringTokenizer st = new StringTokenizer(br.readLine());
        int fst = Integer.parseInt(st.nextToken());
        int sec = Integer.parseInt(st.nextToken());
        int third = Integer.parseInt(st.nextToken());

        max[0] = fst;
        max[1] = sec;
        max[2] = third;

        min[0] = fst;
        min[1] = sec;
        min[2] = third;

        for(int i = 1; i < N; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 3; ++j)
            {
                map[j] = Integer.parseInt(st.nextToken());
            }
            //최댓값
            tmp[0] = map[0] + Math.max(max[0],max[1]);
            tmp[1] = map[1] + Math.max(max[0],Math.max(max[1],max[2]));
            tmp[2] = map[2] + Math.max(max[1],max[2]);

            max[0] = tmp[0];
            max[1] = tmp[1];
            max[2] = tmp[2];

            //최솟값
            tmp[0] = map[0] + Math.min(min[0],min[1]);
            tmp[1] = map[1] + Math.min(min[0],Math.min(min[1],min[2]));
            tmp[2] = map[2] + Math.min(min[1],min[2]);

            min[0] = tmp[0];
            min[1] = tmp[1];
            min[2] = tmp[2];
        }

        int maxAnswer = max[0];
        int minAnswer = min[0];
        for(int i = 1; i < 3; ++i)
        {
            if(max[i] > maxAnswer) maxAnswer = max[i];
            if(min[i] < minAnswer) minAnswer = min[i];
        }

        System.out.printf("%d %d",maxAnswer,minAnswer);
    }

}

📝 풀이

맨위 3칸중 임의의 칸으로 부터 출발하여, 맨 아래칸까지 조건에 맞게 한칸 씩 이동한다 할때, 누적하여 만들 수 있는 최댓값과 최솟값을 출력하는 문제입니다.
열의 갯수는 3개로 제한되어 있으므로, 입력 받음과 동시에 각 층에 도달할 때에 누적하여 쌓인 최댓값과 최솟값을 갱신해주며 N번 반복해주면 마지막에 남은 dp배열의 값들 중 최대, 최솟값을 출력해주어 해결할 수 있습니다.

📜 후기

신나게 구현하고 보니 메모리초과가 떠서 이상했는데, 메모리 제한이 4MB였네요.. ㅎㅎ
슬라이딩 윈도우를 활용한 풀이법이라고 하는데, 사실 dp 말고는 그닥 무슨 알고리즘인지 와닿지가 않아서, 내일 몇 문제 더 풀어볼 생각입니다. 몰랐던 알고리즘을 찾게 되어 기분이 좋네요~.~