[Baekjoon 32931] 자석 놀이 - JAVA

[Silver I] 자석 놀이 - 32931

문제 링크

성능 요약

메모리: 67632 KB, 시간: 524 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 29일 09:23:28

문제 설명

 $2 \times N$ 크기의 격자가 있다. 격자의 각 칸에는 수가 적힌 카드가 하나씩 있다. 맨 왼쪽 위에는 자석이 있고 당신은 이 자석을 상하좌우로 한 칸씩 움직여 맨 오른쪽 아래로 이동시키려고 한다.

자석이 카드 위를 지나면 카드는 자석에 달라붙게 되며, 한 번 붙은 카드는 자석에서 다시 떨어지지 않는다. 자석을 맨 오른쪽 아래까지 이동시켰을 때 자석에 붙은 카드에 적힌 수의 합의 최댓값을 구해보자.

입력

첫 번째 줄에 격자의 열의 개수를 나타내는 수인 $N$이 주어진다. $(2 \leq N \leq 200\ 000)$ 

다음 두 줄에 걸쳐 카드에 적힌 수가 공백으로 구분되어 주어진다. $i+1$번째 줄의 $j$번째 수 $a_{ij}$는 $i$번째 행의 $j$번째 열에 있는 카드에 적힌 수를 나타낸다. $(-10^9 \leq a_{ij} \leq 10^9)$ 

출력

문제의 답을 출력한다.

문제 풀이

DP 문제는 점화식만 생각해내면 된다.

아이디어는 아래와 같다.

1. 한 열씩 처리한다
   • 열을 $1 → 2 → ⋯ → 𝑁$ 순서로 이동
   • 각 열에서 할 수 있는 행동은 아래와 같다.
     • 위쪽 칸만 밟고 지나간다.
     • 아래쪽 칸만 밟고 지나간다.
     • 위·아래 칸 둘 다 방문할 수도 있다(위→아래, 또는 아래→위), 심지어 “위→아래→위”처럼 두 번 교차도 가능하다.
   • 결국 “열 $j$”를 완전히 처리했다 함은, “이 열에 있는 카드(들)를 원하는 순서로 방문”하고서 최종적으로 열 $j$의 위나 아래 중 어느 한 칸에 서 있는 상태”라고 볼 수 있다.
2. 격자 2행이므로 상태 표현이 간단하다.
   열 $j$를 다 처리하고 난 뒤, 행 0(위)에 서 있거나, 행 1(아래)에 서 있을 수 있다.
   이는 곧 2가지 상태로 압축할 수 있음을 의미한다.

이 과정을 “동적 프로그래밍(DP)”으로 풀기 위해, 각 열까지 처리했을 때의 최대 점수를 저장하는 배열을 정의하면 아래와 같다.

$dp[0][j] = j$번째 열까지 처리한 후, $j$번째 열의 위쪽 칸(행 0)에 있을 때 얻을 수 있는 최대 합,
$dp[1][j] = j$번째 열까지 처리한 후, $j$번째 열의 아래쪽 칸(행 1)에 있을 때 얻을 수 있는 최대 합.
$arr[0][𝑗] = j$번째 열의 위쪽 칸(행 0)에 적힌 값,arr[1][𝑗] = $j$번째 열의 아래쪽 칸(행 1)에 적힌 값

따라서 점화식으로 나타내면 아래와 같다.

1. $dp[0][𝑗]dp[0][j]$ (열 $j$가 끝나고 위쪽 행에 있는 경우)
   1. 이전에도 위 → (이번 열 위만)
      • 추가 점수: $arr[0][𝑗]$
      • 결과: $dp[0][j−1]+arr[0][j]$
   2. 이전에도 위 → (이번 열 위·아래 둘 다) → 최종 위
      • 추가 점수: $arr[0][j]+arr[1][j]$
      • 결과: $dp[0][j−1]+arr[0][j]+arr[1][j]$
   3. 이전엔 아래 → (이번 열 위·아래 둘 다) → 최종 위
      • 추가 점수: $arr[0][j]+arr[1][j]$
      • 결과: $dp[1][j−1]+arr[0][j]+arr[1][j]$
        최종적으로 $dp[0][j]=max(dp[0][j−1]+arr[0][j], dp[0][j−1]+arr[0][j]+arr[1][j], dp[1][j−1]+arr[0][j]+arr[1][j])$가 된다.
2. $dp[1][j]$ (열 $j$가 끝나고 아래쪽 행에 있는 경우)
   1. 이전에도 아래 → (이번 열 아래만)
      • $dp[1][j−1]+arr[1][j]$
   2. 이전에도 아래 → (이번 열 위·아래 둘 다) → 아래
      • $dp[1][j−1]+arr[0][j]+arr[1][j]$
   3. 이전엔 위 → (이번 열 위·아래 둘 다) → 아래
      • $dp[0][j−1]+arr[0][j]+arr[1][j]$
        최종적으로 $dp[1][j]=max(dp[1][j−1]+arr[1][j], dp[1][j−1]+arr[0][j]+arr[1][j], dp[0][j−1]+arr[0][j]+arr[1][j])$가 된다.

최종 답은 $dp[1][N]$이 방문 가능한 칸들의 값 합의 최댓값이 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine().trim());

        long[][] arr = new long[2][N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int j = 1; j <= N; j++) {
            arr[0][j] = Long.parseLong(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int j = 1; j <= N; j++) {
            arr[1][j] = Long.parseLong(st.nextToken());
        }

        long[][] dp = new long[2][N+1];

        dp[0][1] = Math.max(arr[0][1], arr[0][1] + arr[1][1]);
        dp[1][1] = arr[0][1] + arr[1][1];

        for (int j = 2; j <= N; j++) {
            long topVal = arr[0][j];
            long botVal = arr[1][j];

            long cand1 = dp[0][j-1] + topVal;
            long cand2 = dp[0][j-1] + topVal + botVal;
            long cand3 = dp[1][j-1] + topVal + botVal;
            dp[0][j] = Math.max(Math.max(cand1, cand2), cand3);

            cand1 = dp[1][j-1] + botVal;
            cand2 = dp[1][j-1] + topVal + botVal;
            cand3 = dp[0][j-1] + topVal + botVal;
            dp[1][j] = Math.max(Math.max(cand1, cand2), cand3);
        }

        long answer = dp[1][N];

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}