[백준] no9465: 스티커

문제

int[2][N] 의 배열에 서로 다른 숫자가 주어진다.

1. 조건: 특정 칸의 숫자를 선택하면, 해당 칸의 상하좌우의 숫자는 선택할 수 없는 값이 된다.
2. 조건: 배열 안에서 합산이 가장 높게 나올 수 있는 숫자들을 선택해야한다.

Input 
테스트_케이스_수 T
배열의_길이 N
배열의_0번째_행에_들어갈_숫자들
배열의_1번째_행에_들어갈_숫자들

Output
합산

문제 링크 : https://www.acmicpc.net/problem/9465

---

원리

DP로 푸는 문제이며, 아래의 점화식을 이해해야 한다.

1. 점화식

: 문제에 주어진 행은 2줄로 고정되므로, 2줄에 대해서 각각 DP를 실행.

: 이 때, 행렬의 [0][0], [1][0]에는 비교를 위해 각각 합산에 영향을 주지않을 0을 대입 후,

  1번째 인덱스부터 입력값을 넣어야 반복 합산에 지장이 없음

: DP라는 합산행렬에서 각 줄의 마지막 칸(N번째)에는 각 줄에서 구할 수 있는 최대값이 저장됨

: 둘 중 더 큰값을 출력

DP[0][N] = Max(DP[1][N-1], DP[1][N-2])

DP[1][N] = Max(DP[0][N-1], DP[0][N-2])

 

2. 그림 설명

첫 번째 칸 : 둘 중 하나만 선택 가능

두 번째 칸 : 1번칸과 대각선인 칸만 선택 가능. DP에는 합산을 적음

세 번째 칸 : 세 번째 칸의 윗칸을 선택하게 되면, 1번째의 아래칸 또는 2번째의 아래칸을 선택하는 선택지 밖에 없음

즉, 아래와 같이 3번째 칸에서 선택하는 칸을 건드리지 않는 경우는 두 가지 방법인 것임

그 중 더 큰 값을 선택해서 DP를 이어가면 됨

네 번째 칸 이후 : 세번째와 같은 방식으로 이어감

---

나의 코드

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T ; i++) {
            int N = Integer.parseInt(br.readLine());
            maxSum(N);        
        }
        bw.close();
    }

    private static void maxSum (int N) throws IOException {
        int[][] map = new int[2][N+1];

        // 입력을 통해 스티커 맵을 완성
        for(int i=0; i<2 ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=1 ; j<=N ;j++) map[i][j] = Integer.parseInt(st.nextToken());
        }

        // 합산한 값을 기록하여 다음 합산에 참고하기위한 이중배열
        int[][]  dp = new int[2][N+1];

        dp[0][1] = map[0][1];
        dp[1][1] = map[1][1];
        
        // 0번째와 1번째를 비교하는 경우가 있어야 하므로 배열을 N+1 길이로 해야함
        for(int i=2; i<=N ; i++) {
            dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + map[0][i];
            dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + map[1][i];
        }
        bw.write(Math.max(dp[0][N], dp[1][N])+ "\n");
    }
}

---

Chat GPT 코드

오늘도 틀리는 너에게 : 문제가 뭔지 알려줘도 못푸는 녀석. 검색이라도 하는 성의를 보여라..

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int[][] board = new int[2][n];

            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < n; k++) {
                    board[j][k] = sc.nextInt();
                }
            }

            int[] stickers = new int[n];
            for (int j = 0; j < n; j++) {
                stickers[j] = board[0][j] + board[1][j];
            }

            int[][] dp = new int[n][4];
            dp[0][0] = 0;
            dp[0][1] = stickers[0];
            dp[0][2] = stickers[1];
            dp[0][3] = Math.max(dp[0][1], dp[0][2]);

            for (int j = 1; j < n; j++) {
                dp[j][0] = Math.max(Math.max(dp[j - 1][0], dp[j - 1][1]), Math.max(dp[j - 1][2], dp[j - 1][3]));
                dp[j][1] = Math.max(dp[j - 1][0], dp[j - 1][2]) + stickers[j];
                dp[j][2] = Math.max(dp[j - 1][0], dp[j - 1][1]) + stickers[j + 1];
                dp[j][3] = Math.max(Math.max(dp[j][1], dp[j][2]), dp[j - 1][3]);
            }

            System.out.println(dp[n - 1][3]);
        }
    }
}

---

레퍼런스 코드

참고 링크 : https://small-stap.tistory.com/11