[자바] 백준 9465 - 스티커 (java)

 문제 : boj9465

---

 

필요 알고리즘 개념

• 동적 계획법 (Dynamic Programming, DP)
  
  • DP로 풀 수 있는 문제이다. DP는 알고리즘이라기 보단 문제 푸는 방식? 같은 거라 생각한다. 어쨌든 어떤건진 미리 알고 풀어야 생각해낼 수 있을 것 같다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

스티커 위치가 아래와 같다고 해보자.

A C E
B D F

이 때, 각 스티커의 가치 중 음수인 것은 없으므로 결국 우측으로 갈수록 무조건 같거나 증가한다.

DP를 활용해 풀면 된다.

각 위치에서 자신의 좌측을 보면서, 어디서 왔을 때 현재 값이 가장 커질지를 확인하면 된다.

예를들어 현재 F 위치라고 보면, 일단 D와 E는 이전값이 될 수 없다.

그럼 좌측으로 한칸 전에서 올 수 있는건 C 뿐이다.

다음은 2칸 전을 보자. A와 B 둘 다 어차피 2칸이 떨어져서 상관없다고 생각할 수 있지만,

조금 더 최적화해보면 어차피 2칸전에 B를 선택했다면, 자동으로 C-F로 오게된다. 이미 C는 볼 것이므로 중복체크가 된다.

반면에 A는 의미가 있는데 A를 선택하면 F를 선택하기 위해 C와 D는 포기해야 하기 때문이다.

따라서 F 위치만 봤을 때 그리디하게 최대값은 F + max(A, C) 라고 볼 수 있다.

마찬가지로 E 위치에서는 E + max(B, D) 이다.

이걸 초반부분에서 ArrayIndexOut.. 이 나지 않도록 적절히 처리해주면 (전 그냥 미리 이전에 2열의 더미값을 두었음) 된다.

최종적으로 답은 맨 마지막 열에 있는 두 값중 큰 값이다.

 

---

 

코드 : github

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            int n = Integer.parseInt(br.readLine());

            // input
            int[][] arr = new int[2][n+2];
            for (int i = 0; i < 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 2; j < n+2; j++) arr[i][j] = Integer.parseInt(st.nextToken());
            }

            // solution
            int answer = 0;
            for (int j = 2; j < n+2; j++) {
                arr[0][j] += Math.max(arr[1][j-2], arr[1][j-1]);
                arr[1][j] += Math.max(arr[0][j-2], arr[0][j-1]);
            }
            sb.append(Math.max(arr[0][n+1], arr[1][n+1])).append('\n');
        }
        System.out.println(sb);
    }
}