[S1] 스티커 9465 : DP

문제

9465번: 스티커

---

풀이 흐름

이 문제는 테스트 케이스의 제한이 없는데 N은 100,000이다. 그러므로 최대한 O(n)으로 풀어야 겠다고 생각했다.

어떻게 최대값을 찾는냐! 스티커는 총 2줄이고 인접한 스티커는 뜯으면 안된다. 만약 열의 수가 짝수이면 지그재그 방법뿐이다. 그래서 2개의 경우의 수 밖에 없지만 문제는 열의 수가 홀수일 때 이다. 

예제를 분석해보면 현재 위치에서 갈 수 있는 방법은 2가지이다. 인접한 변으로 못가니, 대각선으로만 이동이 가능하다. 대각석 이동은 옆칸과 옆옆칸으로 갈 수 있다. 이때 100은 왜 안되지? 생각할 수 있는데 대각선 2개로 100으로 갈 수 있기 때문이다.

 

 

 첫 번째 요소부터 루프를 돌면서 현재 위치에서 존재할 수 있는 누적합(최대합)을 구해 배열에 저장하는 방식을 사용했다.

예를 들어 현재 인덱스가 2라고 할 떄, 대각선 방향으로 0,1번째 요소를 비교하여 둘 중 더 큰 값과 현재 위치의 값(점수)를 더하여 DP[2]에 저장한다. 

이런식으로 차차 DP 배열의 값을 모두 채운다. 그러면 마지막 DP[n]에는 누적된 최대값이 저장된다. DP[n-1]도 최댓값이 될 수 있기에, 두 값을 비교하여 큰 값을 결과로 출력한다. 

 

코드로 확인해보자

코드  - java

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

public class BOJ_스티커 {
    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        while(T>0) {
            T--;
            int N = Integer.parseInt(br.readLine());
            int [][] nums = new int[2][N];
            int [][] dp = new int[2][N];
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            StringTokenizer st2 = new StringTokenizer(br.readLine());

            //nums input
            for(int i=0; i<N; i++) {
                nums[0][i] = Integer.parseInt(st1.nextToken());
                nums[1][i] = Integer.parseInt(st2.nextToken());
            }

            /* solution */
            for(int i=0; i<N; i++) {
                if(i==0) {
                    dp[0][0] = nums[0][0];
                    dp[1][0] = nums[1][0];
                    continue;
                }

                int [] dx = new int[] {-2,-1};
                for(int j=0; j<dx.length; j++) {
                    int x = i +dx[j];
                    int y = 1;
                    if(x>=0 && y>=0) {
                        // 0행
                        dp[0][i] = Math.max(dp[0][i], nums[0][i]+dp[1][x]);
                        // 1행
                        dp[1][i] = Math.max(dp[1][i], nums[1][i]+ dp[0][x]);
                    }
                }
            }

            //max값 찾기
            int max = 0;
            for(int i=N-2; i<N; i++) {
                if(i <0) continue;
                int num = Math.max(dp[0][i], dp[1][i]);
                max = Math.max(max, num);
            }
            bw.write(Integer.toString(max)+"\n");

        }
        bw.flush();
        bw.close();
        br.close();
    }
}