[BOJ] 9465 스티커 (java)

[BOJ] 9465 스티커 (java)

---

1. point & feedback

• 행 0부터 시작, 열 0부터 시작
• dp[0][N] : 0열에서 출발하여 (0, N) 위치까지의 score 의 합
• dp[1][N] : 0열에서 출발하여 (1, N) 위치까지의 score 의 합

• ex) (0,0) 에서 처음 시작했다면 다음 선택할 수 있는 수는 대각선 (1,1) / (1,2) 이다. (0,2), (1,2) 는 선택해봐야 최대 값이 될 수 없음 (0,0) -> (1,1) -> (0,2) 를 가면되니 최대 값이 될 수 없음.

• dp[0][N] = Math.max(dp[1][N-1], dp[1][N-2]) + score[0][N]

  • ex) dp[0][2] 이라 하자. dp[1][1], dp[1][0] 중 하나를 고를 수 있음. 이런식으로 쭉 이어 나가면 점화식 추출
• dp[1][N] = Math.max(dp[0][N-1], dp[0][N-2]) + score[1][N]

---

2. source

package acmicpc;

import java.util.Scanner;

public class Num9465
{
    private static int dp[][]; 

    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int n, score[][];
        for (int i = 0 ; i < T ; i++)
        {
            dp = new int[2][100000];
            n = sc.nextInt();
            score = new int[2][n];

            for (int index = 0 ; index < n ; index++)
                score[0][index] = sc.nextInt();
            for (int index = 0 ; index < n ; index++)
                score[1][index] = sc.nextInt();

            System.out.println(solve(score, n));
        }
    }

    public static int solve(int score[][], int n)
    {
        for (int i = 0 ; i < n ; i++)
        {
            dp[0][i] = Math.max(getDpValue(1, i-1), getDpValue(1, i-2)) + score[0][i];
            dp[1][i] = Math.max(getDpValue(0, i-1), getDpValue(0, i-2)) + score[1][i];
        }
        return Math.max(dp[0][n-1], dp[1][n-1]);
    }

    public static int getDpValue(int x, int y)
    {
        if (x < 0 || y < 0) return 0;

        return dp[x][y];
    }
}