[BOJ/백준] 9465번 - 스티커(Java 풀이/해답)

문제 바로가기: https://www.acmicpc.net/problem/9465

 

백준 Class 4 스티커 문제이다

난이도는 실버 1로 평이한 수준이라 생각한다

조건만 찾아내면 해결할 수 있는 문제였다

---

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다.
상냥이는 스티커를 이용해 책상을 꾸미려고 한다.
상냥이가 구매한 스티커의 품질은 매우 좋지 않다.
스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.
즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

백준 9465번 스티커 문제

모든 스티커를 붙일 수 없게 된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.

먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다.
상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오.
즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커 집합을 구해야 한다.
위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다.
가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 

다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 

연속하는 두 정수 사이에는 빈칸이 하나 있다. 

점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

각 테스트 케이스마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제 입력

2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80

예제 출력

260
290

조건

시간제한: 1초

메모리 제한: 256MB

---

접근

표만 보면 DFS, BFS로 접근해야 할 것만 같은 느낌이라 잠깐 고민해 봤다

하지만, (b) 그림을 보고 합배열로 접근하며 규칙을 찾으면 탐색 없이 진행할 수 있을 것 같았다

사방 탐색을 고려해 보기도 했다만, 합배열이 가장 적합해 보였다

 

아이디어는 심플하다

합배열을 통해 현재 스티커의 최대 점수를 갱신하며 진행한다

마지막 배열 값의 1번 줄, 2번 줄을 비교해 더 큰 값을 선택한다

 

2차원 배열로 구성된 동적 프로그래밍(DP, Dynamic Programming) 문제였다

 

풀이

1. 총 테스트할 T 값을 입력받는다

2. 각 테스트의 N 값을 입력받는다

3. 2차원 배열 arr을 생성하는데, 1부터 사용할 것이기 때문에 new int [2][N+1]로 초기화한다

4. sum 배열도 마찬가지로 생성한다

5. 예제 입력의 정보를 arr 배열에 담는다

   5-1. arr[0][i]에 먼저 넣는다

   5-2. arr[1][i]에도 넣어준다

 

여기까지가 기초 작업이다

다음은 합배열을 초기화해 준다

 

6. sum 배열을 위한 초기값을 넣어준다

   6-1. sum[0][1] 의 값은 arr[0][1]의 값과 같다(처음 시작은 0이고, 그다음은 더하기는 자기 자신이다)

   6-2. sum[1][1] 의 값은 arr[1][1]의 값과 같다

 

다음 핵심 로직을 작성한다

처음 생각을 했을 때, 자기 최댓값은 이전 것을 선택하느냐 안 하느냐에 따라 달렸다고 보았다

따라서 이전 것을 선택한 경우(즉, 반대편 줄의 이전 단계 합배열) 다음과 그림과 같다고 판단했다

 

이걸 2번 인덱스로 확장해 보면?

 

그림이 좀 구리긴 한데...

 

이 친구의 점수를 구하려면?

빨간 별과 파란 동그라미 값을 비교하면 될 것 같았다

sum[0][2] =

 

arr[0][0](이전까지 총 합) + arr[1][1](바로 직전 값의 반대를 선택) + arr[0][2](자기 자신)

vs

arr[1][0] + arr[0][1]

 

이 둘 중 큰 값을 취하면 된다고 봤다

 

반대쪽은 파란 동그라미와 빨간 별 위치를 반대로 바꿔주기만 하면 된다

 

이러면 다음과 같은 식이 도출된다

sum[0][i] =

sum[0][i-2] + arr[1][i-1] + arr[0][i]

vs

sum[1][i-2] + arr[0][i-1]

 

그런데 이렇게만 진행해서 

 

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

 

이 식을 사용하게 되면 예제 1번의 값이 제대로 나오지 않았다

 

원인을 고민해 보니까

1번 예제의 마지막에서 주변을 다 안 고르고 60을 고르는 경우가 있었다

 

따라서 sum[0][3] + arr[1][5] 이런 조건을 또 넣어줘야 했다

같은 라인의 sum[1][3]을 쓰지 않는 이유는, 어차피 저 경우에는 arr[0][4]를 쓰는 게 무조건 점수가 높아지기 때문이다

 

따라서 다음과 같은 조건식이 추가되었다

 

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

 

위의 sum[0][i]만 그림으로 나타내면?(마지막 인덱스 기준)

동그라미는 sum배열, 세모는 arr배열이다

 

이렇게 세 개를 비교하게 된다

따라서 알맞은 점화식을 세워 풀면 마지막 배열에 각각의 최댓값이 나오고

둘 중 더 큰 값을 사용하면 된다

 

이해를 돕기 위한 그림을 넣었는데... 더 이해가 안 될 수도 있을 것 같은 느낌...?

 

코드

package class4;

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

public class 스티커_9465 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(st.nextToken());

        for(int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());

            int[][] arr = new int[2][N+1]; // 배열 생성
            int[][] sum = new int[2][N+1];

            // 1. arr에 정보 입력
            st = new StringTokenizer(br.readLine());
            for(int i = 1; i <= N; i++) {
                arr[0][i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            for(int i = 1; i <= N; i++) {
                arr[1][i] = Integer.parseInt(st.nextToken());
            }

            // 정보 바탕으로 sum 배열 초기화
            sum[0][1] = arr[0][1];
            sum[1][1] = arr[1][1];

            for(int i = 2; i <= N; i++) {
                sum[0][i] = Math.max(sum[0][i-2] + arr[1][i-1] + arr[0][i], 
                	Math.max(sum[1][i-2] + arr[0][i-1], sum[1][i-2] + arr[0][i]));
                sum[1][i] = Math.max(sum[1][i-2] + arr[0][i-1] + arr[1][i], 
                	Math.max(sum[0][i-2] + arr[1][i-1], sum[0][i-2] + arr[1][i]));
            }

            sb.append(Math.max(sum[0][N], sum[1][N])).append("\n");
        }

        System.out.println(sb);
    }
}