[DP] 스티커

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

package com.company;

import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);

    static int testcase; //스티커세트 수
    static int[][] stickerPoint; //각 스티커의 점수
    static int column; //스티커 열의 수
    static int memo[][]; //메모제이션


    public static void main(String[] args) {
        testcase = sc.nextInt();

        //스티커 점수 입력받기
        for(int i=1; i<=testcase; i++){
            column = sc.nextInt();
            stickerPoint = new int[3][column+1];
            initMemo(column); //메모제이션 초기화

            for(int j=1; j<=2; j++){
                for(int k = 1; k<= column; k++){
                    stickerPoint[j][k] = sc.nextInt();
                }
            }//for(j)

            System.out.println( sticker(0,1) );

        }//for(i)

    }

    static void initMemo(int column){

        memo = new int[3][column+1];

        for(int i=0; i<=2; i++){
            for(int j=1; j<=column; j++){
                memo[i][j] = -1;
            }
        }//for(i)

    }


    // status는 지금 줄에서 0:왼쪽에 뗀거없음, 1:왼쪽에 위에꺼 떼어냄, 2:왼쪽아래꺼 떼어냄
    // 'c부터 시작해서 오른쪽'에 있는걸 떼어냈을때 최대점수를 받환
    static int sticker(int status, int c){

        if(c == column+1){
            return 0;
        }

        if(memo[status][c] != -1){
            return memo[status][c];
        }

        int result= sticker(0, c+1);
        if(status==1 || status==0){ result= Math.max( result, sticker(2, c+1) + stickerPoint[2][c] ); }
        if(status==2 || status==0){ result= Math.max( result, sticker(1, c+1) + stickerPoint[1][c] ); }


        memo[status][c] = result;
//        System.out.println("status: " + status+ " c:"+c+ " result:"+result);
        return result;
    }
}

*memo[][]와 stickerPoint[][]는 행렬순서로 되어있는 게 아니라, stiker함수에 맞춰서 배치되어있다. (status에 맞춰 코딩하기 편하도록)

 if(status==1){ result= Math.max( result, sticker(2, c+1) + stickerPoint[2][c] ); }
 if(status==2){ result= Math.max( result, sticker(1, c+1) + stickerPoint[1][c] ); }

위 코드에서  || status==0 를 빠뜨려서 재귀를 돌면서 status가 모두 0이 되는 버그가 생겼었다.