[백준] 3359: 사각 사각 - JAVA

09 Jun 2023 in Algorithm on 다이나믹 프로그래밍

https://www.acmicpc.net/problem/3359

풀이

DP문제이다.

사각형을 각각 가로로 놓을지 세로로 놓을지 정해서 위쪽 둘레의 최댓값을 찾는다.

dp배열을 이차원배열로 만들어 현재 사각형을 가로로 놓는다면 [0]에, 세로로 놓는다면 [1]에 값을 넣는다.

옆면까지 생각해야한다.

이전 dp배열에서 선택안한 변과 현재 선택안한 변의 차이를 더해 최댓값을 현재 dp배열에 더해준다.

---

메모리: 14480KB

시간: 140ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

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());
        int[][] arr = new int[N][2];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[N][2];
        dp[0][0] = arr[0][0];
        dp[0][1] = arr[0][1];
        for (int i = 1; i < N; i++) {
            dp[i][0] = Math.max(dp[i - 1][0] + Math.abs(arr[i - 1][1] - arr[i][1]),
                    dp[i - 1][1] + Math.abs(arr[i - 1][0] - arr[i][1])) + arr[i][0];
            dp[i][1] = Math.max(dp[i - 1][0] + Math.abs(arr[i - 1][1] - arr[i][0]),
                    dp[i - 1][1] + Math.abs(arr[i - 1][0] - arr[i][0])) + arr[i][1];
        }

        System.out.println(Math.max(dp[N - 1][0], dp[N - 1][1]));
    }

}