[백준, 자바] 9465번 - 스티커

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

풀이
처음 한 생각은 그냥 좌대각선 우대각선 중에 큰 값을 골라서 dp[][]에 저장하면 되지 않을까였다.

물론 안된다. 뭘 몰랐냐면, 꼭 인접 대각선 스티커만 선택해야야 최대 점수를 얻지 않기 때문이다.

그래서? 인접한 동서남북을 제외하고 다 비교를 해야 하는 것인가! 생각을 했는데?

그것도 아니다. 일단 연산이 메모이제이션이 아니게 되버리며,
구해야 하는 것은 최댓값 비용인데, 2칸 넘어서 있는 스티커를 고르면 최대값 비용이 나올 수 없다.

위와 같은 경로가 가능하다. 왜 10이나 60은 갈 수없냐고 할 수 있는데, 10 또는 60, 100으로 바로 갈 경우는 문제의 조건에 부합하지 않기 때문이다. 문제가 요구하는 것은 비용의 최댓값을 요구하는 것인데, 10으로 가는 경우는 50 -> 10으로 갈 경우 60이고, 50-> 50 -> 100 -> 10으로 갈 수도 있기 때문에, 60<210으로 바로 갈 수 있는 경우는 고려하지 않는 것이다.
-참고 인용-

참고
https://fbtmdwhd33.tistory.com/76

결과적으로 j가 증가할 때마다 세로로 2줄씩 착착 진행된다고 하면 되겠다.

(이해 잘가네, 출처: https://youngest-programming.tistory.com/442)

스티커의 가로 길이는 유동적이지만, 세로 줄수는 2줄로 고정적이다. 따라서 이중 for문을 쓰지 않고 for문 j 가지고만 처리를 한다.

굳이 long으로 dp를 설정할 필요도 없었다.

궁금증
왜 좌측 대각선의 인접한 두 개의 값만 고려하는 지 모르겠다.
진행방향이 좌-> 우측이라고 가정해서인가.
dp는 그림을 그려서 뇌부터 만들어야 한다는 생각이 든다.

최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 개수

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine()); // 배열의 가로 길이
            int[][] data = new int[2][n + 1];
            int[][] dp = new int[2][n+1];

            // 배열 초기화
            for (int k = 0; k <= 1; k++) { //항상 2줄
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= n; j++) { // 결과적으로 dp는 dp[?][1]부터 시작
                    data[k][j] = Integer.parseInt(st.nextToken());
                }
            }
            // 빠뜨린 부분: 첫 j 줄을 초기화해야 한다.
            dp[0][1] = data[0][1];
            dp[1][1] = data[1][1];
            for(int h = 2; h <= n; h++) {
                dp[0][h] = Math.max(dp[1][h-1], dp[1][h-2]) + data[0][h];
                dp[1][h] = Math.max(dp[0][h-1], dp[0][h-2]) + data[1][h];
            }
            System.out.println(Math.max(dp[0][n], dp[1][n]));
        }
    }
}

이해 안 가는 건 한번 더