[Java] 백준 9465 : 스티커

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

1.

큰 수를 먼저 선택하면 될까? 반례가 존재하고 DP 문제이기에 잘못된 접근 방식이었다.

큰 문제를 작은 문제로 쪼개어 점화식을 세워야 했는데, 어려웠다.

 

 

2.

떼어낼 스티커를 선택하는 방법에는 두 가지가 있다.

 

1. 왼쪽 대각선에 위치한 스티커를 떼어냈을 경우

2. 왼쪽 왼쪽 대각선에 위치한 스티커를 떼어 냈을 경우

 

이 두 가지 경우 중 최대값을 선택하여 dp 배열에 저장한다.

 

여기서 이해가 어려웠던 것은 (1, 3)을 선택하는 경우도 존재 하지 않는가? 였다.

이에 대한 답은, (0, 4)에서 이미 이를 고려했기에 고려하지 않아도 된다.

 

이 두 가지 방법을 점화식을 나타내면 다음과 같다.

 

dp[0][j] = Math.max(dp[1][j - 2], dp[1][j - 1]) + data[0][j];

dp[1][j] = Math.max(dp[0][j - 2], dp[0][j - 1]) + data[1][j];

 

 

 

3.

import java.util.Scanner;

public class Main {
    static int[][] data;
    static int[][] dp;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            data = new int[2][n + 1];
            dp = new int[2][n + 1];

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

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

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

        sc.close();
    }
}

 

 

4.

1시간 가량 고민하였던 문제이다. 개인적으로 고민하는 시간을 1시간 이상 가지지 않는다.

풀릴 것 같은 문제는 그 이상 고민할 가치가 있다고 생각하지만, 답도 안 나오는 문제는 더 고민하면 시간 효율이 떨어진다고 생각한다.

문제를 푸는 아이디어를 배우고 학습(學習)하는 것이 목표이자, 블로그를 개설한 목적이다.

 

[참고] https://zoonvivor.tistory.com/114