[자바] 백준 3359 - 사각 사각 (java)

목차

문제 : boj3359

 

 

필요 알고리즘

• 동적 계획법(DP)
  
  • 사각형을 순서대로 보면서, 점화식을 만들어 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 완전 탐색으로 한번 생각해보자. 각 사각형은 a변이 위로 올라오게 놓거나, b변이 위로 올라오게 놓을 수 있으므로 O(2^n) 으로 구할 수 있다. 이 때 n이 최대 1000 이므로 완전 탐색으론 풀 수 없음을 알 수 있다.

 

  그렇다면 우선 생각해볼 수 있는게 DP이다. 다만 현재 사각형을 놓은 방향이, 그 다음 사각형을 계산할 때 쓰이므로 그리디처럼 매번 a변을 위로, b변을 위로 놓아보고 그 중 최고값을 찾으면 안된다. 즉, 1차원 DP론 안되고, 2차원으로 생각해봐야 한다.

 

  dp[i][x]를 i번 사각형을 x 방향으로 놓았을 때 까지의 최대 위쪽 둘레라고 하자. x는 0일 때 a변을 위로, 1일 때 b변을 위로 향하도록 했다. 그리고 arr[i][0]은 i번 사각형의 a변 길이, arr[i][1]은 i번 사각형의 b변 길이이다. 그렇다면 점화식은 아래와 같이 나온다.

dp[i][0] = arr[i][0]
        + max(dp[i-1][0] + abs(arr[i-1][1] - arr[i][1]), dp[i-1][1] + abs(arr[i-1][0] - arr[i][1]));

dp[i][1] = arr[i][1]
        + max(dp[i-1][0] + abs(arr[i-1][1] - arr[i][0]), dp[i-1][1] + abs(arr[i-1][0] - arr[i][0]));

 

dp[i][0]을 구하는 과정만 말로 풀어서 설명해보면 아래와 같다. (dp[i][1]도 동일한 방식이다.)

- 현재 사각형을 a변이 위로오게 할 때의 최대값은 a변 길이 + max(이전 사각형을 a변을 위로 두었을 때의 최대값 + 이전 사각형 b변과 현재 사각형 b변의 차이, 이전 사각형을 b변을 위로 두었을 때의 최대값 + 이전 사각형 a변과 현재 사각형 b변의 차이)

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[n+1][2];
        int[][] arr = new int[n+1][2];

        StringTokenizer st = new StringTokenizer(br.readLine());
        arr[1][0] = dp[1][0] = Integer.parseInt(st.nextToken());
        arr[1][1] = dp[1][1] = Integer.parseInt(st.nextToken());
        for (int i = 2; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());

            dp[i][0] = arr[i][0]
                    + max(dp[i-1][0] + abs(arr[i-1][1] - arr[i][1]), dp[i-1][1] + abs(arr[i-1][0] - arr[i][1]));
            dp[i][1] = arr[i][1]
                    + max(dp[i-1][0] + abs(arr[i-1][1] - arr[i][0]), dp[i-1][1] + abs(arr[i-1][0] - arr[i][0]));

        }

        System.out.println(max(dp[n][0], dp[n][1]));
    }
}