[백준] 알고리즘 분류(다이나믹 프로그래밍,JAVA)9465번, 스티커

문제 링크

 

9465번: 스티커

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 스티커를 떼면 인접(상하좌우)한 스티커는 찢어집니다.

2. 각 스티커에는 점수가 부여됩니다.

3. 2n개 스티커를 뗄 때 얻을 수 있는 점수의 최대값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 스티커를 떼는 각 순서에서 최대값을 DP[][]에 저장합니다.

 

3. DP[][]에 최대값을 결과로 출력합니다.

 

스티커 최대값 DP탐색!

 

스티커에 대한 행동을 취하는 3가지 경우

 

1. 위에 스티커를 떼기!

스티커 1(떼기)	스티커 3(찢어짐)
스티커 2(찢어짐)	스티커 4

 

2. 아래 스티커를 떼기!

스티커 1(찢어짐)	스티커 3
스티커 2(떼기)	스티커 4(찢어짐)

3. 스티커를 떼지 않고 다음 열로 넘어가기!

스티커 1	스티커 3
스티커 2	스티커 4

 

탐색과정!

 

DP[3][N] 배열을 통해서 각 경우의 최대값을 저장합니다.

 

DP[0][i] : i번째 열에서 3번 행동(스티커 떼지 않기)를 진행했을 때 최대값

DP[1][i] : i번째 열에서 1번 행동(위 스티커 떼기)를 진행했을 때 최대값

DP[2][i] : i번째 열에서 2번 행동(아래 스티커 떼기)를 진행했을 때 최대값

 

DP[][] 계산 점화식!

 

DP[0][i] :  Math.max(DP[1][i-1], DP[2][i-1])

해석 : 스티커를 떼지 않기 때문에 이전에 스티커를 떼었던 값 중 큰 값이 최대값이 됩니다.

 

DP[1][i] :  Math.max(DP[0][i-1], DP[2][i-1]) + i번째 위 스티커 점수

해석 :

위 스티커를 떼려면, 이전에 2번, 3번 행동을 진행해야합니다.

그래서 이전에 스티커를 2번과 3번 행동을 했던 값 중 큰 값에 현재 스티커 점수를 더한 값이  최대값입니다.

 

DP[2][i] :  Math.max(DP[0][i-1], DP[1][i-1]) + i번째 아래 스티커 점수

위 스티커를 떼려면, 이전에 1번, 3번 행동을 진행해야합니다.

그래서 이전에 스티커를 1번과 3번 행동을 했던 값 중 큰 값에 현재 스티커 점수를 더한 값이  최대값입니다.

 

예제입력에 설명을 보시면 진행되는 과정을 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

※1번째 테스트케이스 과정만 보여드리겠습니다.

 

N : 5

 

스티커 정보

 

50	10	100	20	40
30	50	70	10	60

 

2. 스티커를 떼는 각 순서에서 최대값을 DP[][]에 저장합니다.

 

DP[][]탐색!

 

	1	2	3	4	5
행동 3.	0
행동 1.	50
행동 2.	30

	1	2	3	4	5
행동 3.	0	50
행동 1.	50	30 + 10 = 40
행동 2.	30	50 + 50 = 100

 

	1	2	3	4	5
행동 3.	0	50	100
행동 1.	50	30 + 10 = 40	100 + 100 = 200
행동 2.	30	50 + 50 = 100	50 + 70 = 120

 

	1	2	3	4	5
행동 3.	0	50	100	200
행동 1.	50	30 + 10 = 40	100 + 100 = 200	120 + 20 = 140
행동 2.	30	50 + 50 = 100	50 + 70 = 120	200 + 10 = 210

 

	1	2	3	4	5
행동 3.	0	50	100	200	210
행동 1.	50	30 + 10 = 40	100 + 100 = 200	120 + 20 = 140	210 + 40 = 250
행동 2.	30	50 + 50 = 100	50 + 70 = 120	200 + 10 = 210	200 + 60 = 260

 

3. DP[][]에 최대값을 결과로 출력합니다.

 

DP[][]에 최대값 : 260

 

260 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 스터커의 점수를 띄어쓰기 기준 나누었습니다.
• 점화식을 통해 DP[][]의 최대값들을 저장합니다.
• DP[][]에 최대값을 각 테스트케이스 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

 

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        //입력값을 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값을 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] sticker, DP;	//sticker : 스티커 점수, DP : 최대값
        //각 테스트케이스 진행!
        for(int test_case = 0;test_case < T;test_case++){
            int N = Integer.parseInt(br.readLine());
            sticker = new int[2][N];
            DP = new int[3][N];
            //스티커 정보 저장
            for(int i=0;i<2;i++){
                st = new StringTokenizer(br.readLine()," ");
                for(int j=0;j<N;j++)
                    sticker[i][j] = Integer.parseInt(st.nextToken());
            }
            //DP초기값 초기화
            DP[1][0] = sticker[0][0];
            DP[2][0] = sticker[1][0];
            //DP값 점화식으로 저장하기!
            for(int i=1;i<N;i++){
                DP[0][i] = Math.max(DP[1][i-1], DP[2][i-1]);
                DP[1][i] = Math.max(DP[0][i-1], DP[2][i-1]) + sticker[0][i];
                DP[2][i] = Math.max(DP[0][i-1], DP[1][i-1]) + sticker[1][i];
            }
            //DP의 최대값 BufferedWriter 저장
            bw.write(Math.max(DP[1][N-1], DP[2][N-1]) + "\n");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}