[백준 9465번 스티커]

728x90

오늘의 문제는 스티커이다.

 

 

#고민의 흐름

처음엔 무조건 완전탐색!

 

처음에 문제를 읽었을 때에는 dfs나 bfs 등으로 한 곳 점수 더하고,

그 칸과 주변까지 방문처리해 주고 반복하는 방식을 떠올렸었다.

 

하지만 n의 구간이 10만까지인 점을 고려하면 무조건 시간초과가 날 것 같았다.

 

어떻게 하는 게 좋을지 고민하던 중 구간별 최고점수를 기록하며 나아가는 Bottom-Up DP 방식이 떠올랐다.

dp 배열을 어떻게 만들지 메모장을 켜고 한참을 고민하다가 문제를 풀었다.

사진과 함께 설명해 나가겠다! ( 예제는 예제 문제 1번을 사용하였다. )

일단, dp배열을 만들 때 이전값을 참고하기 때문에 dp [0]의 경우 Array오류가 날 수 있어 애초에 n + 1으로 선언해 주었다.

또한, arr배열도 매번 Index신경 쓰기 귀찮으니 이것도 1 ~ n+1로 입력을 해주었다.

 

dp배열의 0행, 1행은 각자 교차되는 arr배열의 0행, 1행을 더해준다.

(ex. dp [0][i] = dp [1][i-1] + arr [0][i]; )

 

dp배열의 2행은 1열 이전의 dp배열의 0행과 1행 중 최댓값을 넣어준다.

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

 

✨dp배열 0행과 1행 값들 중 각각 dp배열 2행 + arr배열 0행 or 1행 값보다 작다면 바꿔준다.

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

 

위처럼 dp [0][i]와 dp [1][i]는 각자 교차되는 [i-1]의 값을 더해준다.

 

dp [2][i]는 dp [0][i-1]과 dp [1][i-1] 중 큰 수로!

 

dp배열을 채우다 보면 이렇게 된다.

이제 마지막 칸을 채워야 하는데, 이때 위 규칙 설명 중 ✨이 달려있는 규칙이 적용된다.

( 한 칸 고르지 않은 경우가 더 큰 점수결과를 만드는 경우! )

 

이전 규칙처럼 dp [0][i]와 dp [1][i]를 채운다면 위와 같다.

하지만 위의 ✨규칙을 보자.

 

✨dp배열 0행과 1행 값들 중 각각 dp배열 2행 + arr배열 0행 or 1행 값보다 작다면 바꿔준다.

 

즉, i-1에 점수를 획득하지 않았다면, 200점이고 이번에 arr의 [0]과 [1] 중 아무거나 가능하다는 말이다.

그렇다면 dp [0][i]는 dp [2][i-1] + arr [0][i] = 240 하지만 기존방식이 더 크기 때문에 패스.

dp [1][i]는 dp [2][i-1] + arr [1][i] = 260 현재 dp [1][i]보다 크기 때문에 대체해 준다!

배열을 마저 채워주면 아래와 같다.

 

여기까지 왔다면 dp [0][i]와 dp [1][i] 중 큰 수가 답이 되겠다.

 

 

코드는 다음과 같다.

( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )

( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )

import java.util.*;
import java.io.*;
public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main (String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int arr[][], dp[][];
        for(int t = 0; t<tc; t++){
            int n = Integer.parseInt(br.readLine());
            arr = new int [2][n + 1];
            dp = new int [3][n + 1];
            for(int i = 0; i<2; i++){
                st = new StringTokenizer(br.readLine());
                for(int j = 1; j<n + 1; j++){
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            //여기까지가 입력 !
            
            //1부터 n까지 배열을 채워간다
            for(int i = 1; i<n + 1; i++){
            	//dp[0]과 dp[1]칸은 교차로 arr값을 더해주며 배열을 채우고,
                dp[0][i] = dp[1][i-1] + arr[0][i];
                dp[1][i] = dp[0][i-1] + arr[1][i];
                
                //dp[2][i-1]값에 각 수를 더한 값이 지금보다 더 크다면 바꾼다.
                dp[0][i] = Math.max(dp[0][i], dp[2][i-1] + arr[0][i]);
                dp[1][i] = Math.max(dp[1][i], dp[2][i-1] + arr[1][i]);
                
                //dp[2][i] 값은 [i-1]의 두 값중 더 큰애로 !
                dp[2][i] = Math.max(dp[0][i-1], dp[1][i-1]);
            }
            
            //출력을 위해 sb에 append! 줄바꿈도 잊지말자.
            sb.append(Math.max(dp[0][n], dp[1][n])).append("\n");
        }
        //출력하면 끝.
        System.out.print(sb);
    }
}

 

DP문제를 만나고 한참을 고민만 하다가 검색찬스를 쓴 경우도 많았는데

이번 문제는 혼자서 DP문제임을 알고, 표도 잘 만들어서 채워나가고 답까지 한 번에 맞춰서 기분이 좋았다.

앞으로 만날 DP문제들도 잘(?) 풀 수 있을 것만 같다.

 

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~

 

https://www.acmicpc.net/problem/9465