[백준 9465, Java] 스티커

문제

www.acmicpc.net/problem/9465

9465번: 스티커

 

 

풀이

 이 문제에서 실수하기 쉬운 부분은 c번째 열에 있는 스티커를 선택하지 않을 수도 있다는 점이다. 

f(n,m)을 n번째 열의 m번째 스티커를 선택했을 때의 스티커 총합의 최대라고 정의하자. m=0인 경우는 스티커를 선택하지 않을 때, m=1은 1번째 행의 스티커를 선택했을때, m=2는 2번째 행의 스티커를 선택했을 때의 최대값이다. 

 

 n번째 열에서 어떤 스티커를 선택할 수 있는 지 선택할 수 없는지는 n-1번째 열에서 어떤 스티커를 선택했는지에 따라 달라진다. 만약 n번째 열에서 스티커를 선택하지 않으면 n-1번째 열에는 스티커를 선택할 수도 있고, 선택하지 않을 수도 있다. n번째 열에서 1번째 행을 선택하는 경우, n-1 번째 열에서는 2번째 행을 선택하거나 스티커를 선택하지 않을 수 있다. 

 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[][] scores;
    public static int[][] maxScores;

    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for(int t = 0 ; t<T ; t++){
            N = Integer.parseInt(br.readLine());
            scores = new int[3][N+1];
            maxScores = new int[N+1][3];      //n열에서 스티커를 고를 때, 아무것도 안고르는 경우(0), 1번쨰 행의 스티커를 고르는 경우, 2번째 행의 스티커를 고르는 경우 에 따른 최대값

            //score초기화
            for(int i = 1; i<=2; i++ ){
                st = new StringTokenizer(br.readLine(), " ");
                for(int j = 1; j<=N; j++ ){
                    scores[i][j] =Integer.parseInt(st.nextToken());
                }
            }

            int result = getMax();
            bw.write(String.valueOf(result)+"\n");
            bw.flush();


        }
        br.close();
        bw.close();
    }
    public static int getMax(){
        for(int column = 1; column<=N; column++){
            if (column==1){
                maxScores[1][0] = 0;
                maxScores[1][1] = scores[1][1];
                maxScores[1][2] = scores[2][1];
            }
            else{
                maxScores[column][0] = Math.max(maxScores[column-1][0],Math.max(maxScores[column-1][1], maxScores[column-1][2]));
                maxScores[column][1] =Math.max(maxScores[column-1][0], maxScores[column-1][2]) + scores[1][column];
                maxScores[column][2] =Math.max(maxScores[column-1][0], maxScores[column-1][1]) + scores[2][column];
            }
        }

        return Math.max(maxScores[N][0],Math.max(maxScores[N][1], maxScores[N][2]));
    }
}