[백준] 동적 프로그래밍 - 9465번 스티커 (Java)

문제링크

9465번: 스티커

 

접근한 방법

• 동적 프로그래밍

 

---

풀이 방법

• 2행이므로 열마다의 경우의 수를 고려해보면 된다.
  열 하나에서 생각해볼 수 있는 경우의 수는 아래와 같이 3가지이다.
• 왼쪽부터 탐색

0	1	2
X	O	X
X	X	O

X : 스티커를 뜯지 않음  |  O : 스티커를 뜯음

 

• 이를 토대로 a[경우의 수 인덱스(크기 3)][스티커 열의 인덱스(크기 n)] 배열로 점화식을 세운다.
  편의상 $a_{i,col}$라 하자.
  $a_{i,col}$ : col열의 i경우에 따라 스티커를 뜯었을 때의 최대값
• e.g)
  $a_{(0,col)}$ : 자기 열의 스티커를 모두 뜯지 않았을 때, 스티커들의 합
  $a_{(1,col-1)}$ : 자기 열 왼쪽의 0번째 행 스티커를 뜯었을 때, 스티커들의 합
• 입력으로 주어진 스티커는 sticker[행(크기 2)][열(크기 n)]이며, $sticker_{(2,n)}$으로 표현해보자.

 

경우 1 i=0일 때 (자기 열의 0행과 1행 모두 스티커를 뜯지 않을 때)

자기 기준 왼쪽 열의 스티커 중, 3가지 경우에 따라 가장 큰값을 저장한다.

 

$a_{(0,col)} = max(a_{(0,col-1)}, a_{(1,col-1)}, a_{(2,col-1)})$

 

경우 2 i=1일 때 (자기 열 0행의 스티커를 뜯었을 때)

자기 기준 왼쪽을 모두 뜯지 않거나, 왼쪽 아래를 뜯는 경우 중 큰 값에 + 자기 열의 0번째 행 스티커 점수를 더한다.

 

$a_{(1,col)} = max(a_{(0,col-1)}, a_{(2,col-1)}) + sticker_{(0,col)}$

 

 

경우 3 i=2일 때 (자기 열 1행의 스티커를 뜯었을 때)

자기 기준 왼쪽을 모두 뜯지 않거나, 왼쪽 위를 뜯는 경우 중 큰 값에 + 자기 열의 1번째 행 스티커 점수를 더한다.

 

$a_{(2,col)} = max(a_{(0,col-1)}, a_{(1,col-1)}) + sticker_{(1,col)}$

 

-결론

위 점화식에 따라, a의 맨 마지막 열의 최댓값을 출력하면 된다.

---

소스코드 작성 방법

• col = 0일 때, a[0][0]은 아무것도 뜯지 않는 상태이므로 0
  a[1][0]과 a[2][0]은 각각 sticker[0][0], sticker[1][0]의 값을 갖는다.
• 내가 했던 실수 : 배열 a의 크기를 sticker.length로 하여, 크기가 2로 되었었다.
• for문은 col = 1부터 시작하여 n까지 탐색한다. (왼쪽에서 오른쪽 방향으로 탐색)

 

소스코드

package baekjoon.dp;
import java.io.*;
import java.util.StringTokenizer;

public class Q_9465_Stricker {
    public static int solution(int[][] sticker){
        int n = sticker[0].length;
        int[][] a = new int[3][n];
        int max = 0;
        
        a[0][0] = 0;
        a[1][0] = sticker[0][0];
        a[2][0] = sticker[1][0];

        for(int col=1 ; col<n; col++){
            a[0][col] = Math.max(a[0][col - 1], Math.max(a[1][col - 1], a[2][col - 1]));
            a[1][col] = Math.max(a[0][col - 1], a[2][col - 1]) + sticker[0][col];
            a[2][col] = Math.max(a[0][col - 1], a[1][col - 1]) + sticker[1][col];
        }

        max = Math.max(a[0][n-1], Math.max(a[1][n-1], a[2][n-1]));

        return max;

    }
    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()); // 테스트 케이스 개수
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine()); // n열
            StringTokenizer st = new StringTokenizer(br.readLine());
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int[][] sticker = new int[2][n]; // 스티커 점수
            for (int col = 0; col < n; col++) {
                sticker[0][col] = Integer.parseInt(st.nextToken());
                sticker[1][col] = Integer.parseInt(st2.nextToken());
            }

            bw.write(solution(sticker) + "\n");
        }
        br.close();
        bw.close();
    }

}