[백준] 9465: 스티커 - Java (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

이 문제는 '현재 아이템을 선택할 경우와, 하지 않을 경우를 생각해서 최댓값을 할당해라' 이다.

 

 

bottom-up, top-down 방식으로 볼 수 있는데, 이번 문제는 top-down 으로 보는 것이 이해하기 쉽다.

각 아이템이 선택될 경우 그 전 아이템을 비교하는 것이다. 무슨 말이냐면 

 

 

40을 선택하기 전 아이템을 생각해 보면 70에서 넘어오거나, 10에서 넘어오는 것, 둘 중 하나이다.

 

근데 우리는 dp 배열에 원본 데이터가 아닌 더한 값을 저장하니 실질적으로는 3번 인덱스의 100과 10이 더해진 110과 비교를 하게 될 것이다. 우리는 쉽게 그냥 큰 값을 dp[i][j]에 더하면 되는 것이다.

 

 

그리고 이렇게 하는 것이 이해하기 어렵게 말하자면 해당 인덱스에서 '한 아이템을 선택할지, 한 아이템을 선택하지 않을지, 아니면 둘 다 선택하지 않을지'를 생각해서 최댓값을 저장하는 것이다. 

 

 

처음부터 차근차근 단계별로 확인해 보자.

 

 

1. 1번과 2번 그리고 1번과 2번을 비교해서 큰 값을 해당 아이템과 더해서 각각 dp[2][1], dp[2][2] 에 할당.

 

 

 

 

2. 각각 1번과 2번에서 더 큰 값을 각각의 this 와 더한 뒤  dp[3][1], dp[3][2]에 할당한다.(반복)

 

 

 

 

3.

 

 

 

4. 

 

 

 

 

끝났다면 이제 dp[n][1]과 dp[n][2]를 비교해서 큰 값을 출력하면 된다.

이 예제의 경우 dp[n][2]가 출력될 것이다.

 

 

 

  풀이

 

 

package src.DP;

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

public class 스티커_9465 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        int[][] stikers;
        int[][] dp;


        // TestCase
        for(int i = 1; i <= t; i++){

            // ------Input------
            int n = Integer.parseInt(br.readLine());

            stikers = new int[n + 1][2];
            dp = new int[n + 1][2];


            // 첫째 줄 Input
            StringTokenizer st_firstLine = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++){
                stikers[j][0] = Integer.parseInt(st_firstLine.nextToken());
            }
            // 둘째 줄 Input
            StringTokenizer st_secondeLine = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++){
                stikers[j][1] = Integer.parseInt(st_secondeLine.nextToken());
            }


            // ------Solution------

            // dp 초기값 설정
            dp[1][0] = stikers[1][0];
            dp[1][1] = stikers[1][1];


            for(int j = 2; j <= n; j++){
                dp[j][0] = stikers[j][0] +  Math.max(dp[j - 1][1], dp[j - 2][1]);
                dp[j][1] = stikers[j][1] +  Math.max(dp[j - 1][0], dp[j - 2][0]);
            }

            sb.append(Math.max(dp[n][0], dp[n][1])).append('\n');

        }

        System.out.println(sb);

    }
}