[Algo] 백준 3359 사각 사각 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/3359

메모리 : 14656KB

시간 : 148ms

언어 : Java 11

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] dp = new int[N + 1][2]; // 눕혔을 때 세웠을 때
        int[][] arr = new int[N + 1][2];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        dp[1][0] = arr[1][0];
        dp[1][1] = arr[1][1];
        for (int i = 2; i <= N; i++) {
            // 눕혔을 때 0
            // 전 칸 눕혔을 때 + 새로 눕힌 사각 + 단차로 생긴 옆 벽(전 칸의 옆 벽-현재 칸의 옆 벽)
            // 전 칸 세웠을 때 + 새로 눕힌 사각 + 단차로 생긴 옆 벽
            // 둘 중 더 큰 것
            dp[i][0] = Math.max(dp[i - 1][0] + arr[i][0] + Math.abs(arr[i - 1][1] - arr[i][1]),
                    dp[i - 1][1] + arr[i][0] + Math.abs(arr[i - 1][0] - arr[i][1]));
            // 세웠을 때 1
            dp[i][1] = Math.max(dp[i - 1][0] + arr[i][1] + Math.abs(arr[i - 1][1] - arr[i][0]),
                    dp[i - 1][1] + arr[i][1] + Math.abs(arr[i - 1][0] - arr[i][0]));
        }
        System.out.println(Math.max(dp[N][0], dp[N][1]));
    }
}

 

풀이

사각의 두 변 중 어느 쪽을 바닥으로 놓느냐에 따라 값이 달라지기 때문에, 두 변을 모두 바닥에 놔 보면서 큰 값을 저장해가면 된다.