[백준 *Java] - 스티커 (9465)

 

스티커 문제보기

9465번: 스티커

문제 설명
상근이의 여동생 상냥이는 문방구에서 2n개를 구매했다.
스티커는 그림(a)와 같이 2행 n열로 배치되어 있다.
상냥이는 스티커를 이용해 책상을 꾸미려 한다.
상냥이가 구매한 스티커의 품질은 매우 좋지 않다.
스티커 한장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.
즉, 뗀 스티커의 왼쪽, 오른쪽, 위 와래에 있는 스티커는 사용할 수 없게 된다.
모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.
먼저, 아래 그림 (b)와 같이 각 스티커에 점수를 매겼다.
상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오.
즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커 집합을 구해야한다.
아래의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이것이 최대 점수이다.
가장 높은 점수를 가지는 두 스티커(100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 <= n <= 100,000)이 주어진다.
다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다.
연속하는 두 정수 사이에는 빈 칸이 하나 있다.
점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

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

---

👇 접근방식

제가 생각한 로직을 테스트케이스 첫 번째 걸로 설명을하자면, 

 

	0	1	2	3	4
	50	10	100	20	40
	30	50	70	10	60
0	50	100	200	210	250
1	30	40	110	130	190
2	0	0	130(100+30)	120(20+[50+50])	150 40+[70+10+30]
3	0	0	120(70+50)	50(10+[10+30])	260 60+[100+50+50]

이런식으로 문제에 나온 높은 수를 가진 두 스티커가 변을 공유할 때를 생기는 변수까지도 배열 인덱스에 담아 비교를 합니다.

따라서, 결국 마지막 에 도출된 값에서 제일 큰 값을 고르면 됩니다.

---

아래에 코드는 실패라고 뜬 코드입니다.

테스트케이스는 맞지만, 제출하니깐 틀렸다고 나오네요.

로직상 오류가 있었네요.아래 로직으로 하게 될 경우 문제에서 언급했던, 높은 수를 가진 두 스티커가 변을 공유할 때를 생기는 변수를

DP[2][J] 와 DP[3][J] 로 잡아 주었다고 생각을 했는데,

그리고 테스트케이스로 코드 구현 전에, 종이에다가 확인까지 하였지만 오류가 있었습니다.

아래 코드는 위에 노란 마킹 되어있는 상황이 한 번일 경우는 정답처럼 나오지만,

여러 개일 경우 현 코드 로직에는 문제가 생기게 됩니다. 테스트케이스에서 한 번만 있다보니 맞는 로직이라 생각하고 반례랑 다른 테스트케이스를 만들어서 확인해보지 않고 바로 설계된 걸 구현 했습니다.

문제가 무엇인 지 발견했으니, 다시 코드를 설계할 생각입니다.

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

public class Main {
    static long DP [][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int arr [][] = new int[2][N+1];
            DP = new long[4][N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) arr[0][i] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) arr[1][i] = Integer.parseInt(st.nextToken());

            DP[0][0] = arr[0][0];
            DP[1][0] = arr[1][0];
            for (int i = 1; i < N; i++) {
                DP[0][i] = DP[1][i-1] + arr[0][i];
                DP[1][i] = DP[0][i-1] + arr[1][i];
                if (i > 1) {
                    DP[2][i] = DP[1][i-2] + arr[0][i];
                    DP[3][i] = DP[0][i-2] + arr[1][i];
                }
            }
            System.out.println(Math.max(DP[3][N-1],Math.max(DP[2][N-1],Math.max(DP[0][N-1],DP[1][N-1]))));
        }
    }
}

 

 

코드를 살짝만 바꿔주어도 로직 설계 했을 때 놓쳤던 바로 부분을 잡을 수 있었습니다.

아래 코드는 성공한 코드입니다.

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

public class Main {
    static long DP [][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            long arr [][] = new long[2][N+1];
            DP = new long[2][N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) arr[0][i] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) arr[1][i] = Integer.parseInt(st.nextToken());

            DP[0][0] = arr[0][0];
            DP[1][0] = arr[1][0];

            for (int i = 1; i < N; i++) {
                DP[0][i] = DP[1][i-1] + arr[0][i];
                DP[1][i] = DP[0][i-1] + arr[1][i];
                if (i > 1) {
                    DP[0][i] = Math.max(DP[1][i-2] + arr[0][i], DP[0][i]);
                    DP[1][i] = Math.max(DP[0][i-2] + arr[1][i], DP[1][i]);
                }
            }
            System.out.println(Math.max(DP[0][N-1], DP[1][N-1]));
        }
    }
}