[BOJ] 9465 - 스티커

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/9465

9465번: 스티커

난이도: 실버 2

사용언어: JAVA

 

풀이

전형적으로 다이나믹 프로그래밍을 이용하여 해결하는 문제이고, 구현도 어렵지 않습니다.

 

왼쪽부터 다이나믹 프로그래밍을 위한 dp라는 배열을 채워나갈 텐데, 다음과 같은 규칙을 갖습니다. 바로 A칸에 들어갈 dp의 값은 1번 칸까지의 dp 값과, 2번 칸까지의 dp 값과, 3번 칸까지의 dp 값 중 가장 큰 값에 자기 자신의 점수를 더한 값이라는 것입니다. 당연히 바로 밑의 칸도 같은 느낌으로 구현이 가능합니다.

 

dp[0][i] = arr[0][i]+ Math.max(dp[1][i-1],Math.max(dp[0][i-2],dp[1][i-2]));
dp[1][i] = arr[1][i] + Math.max(dp[0][i-1],Math.max(dp[0][i-2],dp[1][i-2]));

 

이 규칙만 캐치할 수 있으면, 문제는 쉽게 해결할 수 있습니다.

 

import java.io.*;
import java.util.*;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int T = Integer.parseInt(br.readLine());
        int N;
        int[][] arr;
        int i;
        int max = 0;
        StringTokenizer st;
        while (T > 0) {
            N = Integer.parseInt(br.readLine());
            arr = new int[2][N];
            int[][] dp = new int[2][N];
            st = new StringTokenizer(br.readLine());
            for (i = 0; i < N; i++) {
                arr[0][i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (i = 0; i < N; i++) {
                arr[1][i] = Integer.parseInt(st.nextToken());
            }
 
            dp[0][0] = arr[0][0]; // dp의 첫 칸은 당연히 자기 자신의 점수
            dp[1][0] = arr[1][0];
            if (N >= 2) { // 두 번째 칸까지는 직접 채워넣어준다.
                dp[0][1] = dp[1][0] + arr[0][1];
                dp[1][1] = dp[0][0] + arr[1][1];
            } else { // 만약 N이 1이라면 예외 처리
                bw.write(String.valueOf(Math.max(dp[0][0], dp[1][0])) + "\n");
                continue;
            }
 
            for (i = 2; i < N; i++) { // 위에서 언급한 수식 사용
                dp[0][i] = arr[0][i] + Math.max(dp[1][i - 1], Math.max(dp[0][i - 2], dp[1][i - 2]));
                dp[1][i] = arr[1][i] + Math.max(dp[0][i - 1], Math.max(dp[0][i - 2], dp[1][i - 2]));
                max = Math.max(max, Math.max(dp[0][i], dp[1][i])); // 지금까지의 최댓값 저장
            }
            bw.write(String.valueOf(max) + "\n"); // 최댓값을 출력하고
            max = 0; // max 값 초기화
            T--;
        }
        bw.flush();
        bw.close();
        br.close();
    }
}