[백준][DP][9465]스티커

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

- 소스코드

public class Main {
	
	public static void main(String[] args) throws FileNotFoundException {
		//Scanner sc = new Scanner(System.in);
		Scanner sc = new Scanner(new FileInputStream("input.txt"));

        	int cases = sc.nextInt();
        	int[][] answerArr;
        	int N;
        	int[][] arr;
        
        	while(cases-- > 0){

        		N=sc.nextInt();
        		arr=new int[2][N];
        		for(int i=0; i<2; i++){
        			for(int j=0; j<N; j++){
        				arr[i][j]=sc.nextInt();
        			}
        		}

        		answerArr=new int[N][3];
        		answerArr[0][0]=0;
        		answerArr[0][1]=arr[0][0];
        		answerArr[0][2]=arr[1][0];
        	
         		for(int i=1; i<N; i++){
        			for(int j=0; j<3; j++){
        				switch(j){
        					case 0 : answerArr[i][j]=Math.max(Math.max(answerArr[i-1][0],answerArr[i-1][1]),answerArr[i-1][2]);
        						 break;
        					case 1 : answerArr[i][j]=Math.max(answerArr[i-1][0],answerArr[i-1][2])+arr[0][i];
        						 break;
        					case 2 : answerArr[i][j]=Math.max(answerArr[i-1][0],answerArr[i-1][1])+arr[1][i];
        						 break;
        				}
        			}
        		}
        		System.out.println(Math.max(Math.max(answerArr[N-1][0],answerArr[N-1][1]),answerArr[N-1][2]));
        	}
        	sc.close();
	}
}

-My Thinking

비교적 단순한 점화식을 이용해서 풀 수 있는 문제 였음.

-Logic

제일 첫 번째 열부터 마지막 열까지 해당 열의 스티커를 뜯지 않은 경우와 위에를 뜯었을 때와 아래를 뜯었을 때의 최대값들을 모두 저장해서

마지막에 누적 된 최대값을 구한다.