[알고리즘 PS] 백준 9465 스티커 자바 문제 풀이

문제

해당 포스팅은 백준의 9465번 스티커 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

스티커 문제는 백준의 계단 오르기 문제와 비슷한 논리로 풀 수 있다.

계단 오르기는 1차원 배열이었고, 이번 스티커 문제는 2차원 배열이라고 생각하면 된다.

 

점화식 자체를 도출해내는 방법은 크게 어렵지 않았지만 2차원 배열을 다루는데에 조금 아쉬운 점들이 있던 문제였다.

시작해보자.

접근법

동적 프로그래밍에서 핵심은 현재 단계(배열의 인덱스)의 값을 구하려면 이전의 어떤 단계(배열의 이전 인덱스)들을 더하면 될지를 생각하면 쉽게 풀릴 수 있다.

 

스티커의 가중치가 최대로 되려면 큰 수만 보고 뽑으면 된다.

하지만 제약 조건 하나가 추가된다.

 

• 한 장을 떼면 해당 스티커와 변을 공유하는 스티커는 모두 찢어져 사용 불가.

이 말은 [n][m] 칸에 스티커를 뗀다면 [n-1][m] [n+1][m], [n][m+1]의 스티커는 사용하지 못한다는 뜻이다.

그럼 [n][m] 번 째 스티커는 무조건 [n-1][m] 스티커와 함께 쓰일 수 밖에 없다.

기호로 하니 헷갈릴 수 있는데, 이 말은 현재 뜯으려는 스티커의 대각선 스티커만 함께 뜯을 수 있다는 뜻이다.

 

또한 n-2번째 스티커는 대각선이던 아니던 둘 다 쓸 수 있으므로, n-2 번째 열의 스티커를 포함한 현재 가중치와 n-1번째 대각선 스티커를 포함한 현재 가중치 중 더 큰 수를 뽑으면 해결할 수 있는 문제이다.

 

그림으로 보면,

 

이와 같은 배열에 100이라는 수가 쓰이기 위해서는 아래 표처럼 파란색의 수만 가능하다는 것이다.

 

 

그리고 이들의 최대에서 현재 보고있는 스티커의 합을 누적해주고 반복을 돌리면 된다.

주의하자

이 배열의 반복을 다루기 위해서는 우리가 일반적으로 알고 있는 2중 for loop에서 조금 더 생각해야 한다.

for (int i = 0; i < arr[0].length; i++) {
    for (int j = 0; j < 2; j++) {
        System.out.println(arr[j][i]);
    }
}

정답 코드

public class Main {
    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());
        while(t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[][] d = new int[2][100001];
            String[] column = br.readLine().split(" ");
            d[0] = strArrToIntArr(column, n);
            column = br.readLine().split(" ");
            d[1] = strArrToIntArr(column, n);

            d[0][1] += d[1][0];
            d[1][1] += d[0][0];
            for(int i = 2; i < n; i++) {
                for(int j = 0; j < 2; j++) {
                    if(j == 0) {
                        d[j][i] += Math.max(d[1][i-1], Math.max(d[0][i-2], d[1][i-2]));
                    }else {
                        d[j][i] += Math.max(d[0][i-1], Math.max(d[0][i-2], d[1][i-2]));
                    }
                }
            }

            bw.write(findMaxNum(d) + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static int findMaxNum(int[][] arr) {
        int max = 0;
        for (int i = 0; i < arr[0].length; i++) {
            for (int j = 0; j < 2; j++) {
                max = Math.max(arr[j][i], max);
            }
        }
        return max;
    }

    private static int[] strArrToIntArr(String[] arr, int size) {
        int[] ret = new int[arr.length];
        for(int i = 0; i < size; i++){
            ret[i] = Integer.parseInt(arr[i]);
        }
        return ret;
    }
}

---

문제 회고

회고

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.