스티-커

스티-커

백준 9465번 문제

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

9465번: 스티커

 

 

 

 

1. 문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

 

[스티커]

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

 

입력

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

 

출력

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

 

 

예제 입력 1 

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

 

 

예제 출력 1 

260
290

 

 

 

 

2. 풀이

■ 풀이 방법

왼쪽 열부터 1행과 2행 둘 중 하나의 스티커를 뜯거나 아무것도 뜯지 않는다고 하자.

이때, 가장 마지막에 [뜯겨지는] 스티커는 맨 오른쪽 열의 1행 또는 2행의 스티커일 것이다.

 

오른쪽 마지막 열의 스티커가 뜯기지 않는 결과에는 "절대로" 도달할 수 없다.

왜냐하면.. 이 문제는 스티커를 뜯어서 "최대"의 점수를 구하는 문제이기 때문이다.

 

2xn 스티커의 맨 오른쪽 열을 n번째 열이라고 했을 때 n-1의 스티커들을 생각해보자.

n-1열의 스티커가 될 수 있는 상태는 다음과 같이 3가지이다.

 

● 1행의 스티커가 뜯긴다.

● 2행의 스티커가 뜯긴다.

● 어느 것도 뜯기지 않는다.

 

1행의 스티커가 뜯기는 경우(= (1, n-1)) (2, n)(= 마지막 열 2행의 스티커)의 스티커를 뜯어야 점수가 상승하기 때문에

무조건!

점수의 합을 최댓값으로 만들려면 (2, n)의 스티커를 [뜯어야]한다.

 

마찬가지의 이유로 2행의 스티커(= (2, n-1))가 뜯기는 경우도 (1, n)의 스티커를 [뜯어야]한다..

 

마지막으로 n-1열의 스티커가 어느 것도 뜯기지 않을 경우.

이 경우도 점수를 최대로 만들려면 (1, n)과 (2, n)의 스티커 중 점수가 높은 스티커를 [뜯어야]한다.

 

점수를.. 최대로 만들려면!

마지막 열의 스티커는 반드시 [뜯겨질 수] 밖에 없는 것이다..!

 

이로써 마지막에 일어날 일은 [두 가지]로 정해졌다.

 

그렇다면 이제부턴 이 [두 가지]일에 대해서만 생각해보자.

먼저!

(1, n)의 스티커가 [뜯겨질] 경우

n-1열에서 벌어질 일은 놀랍게도 단 두 가지다..

 

● 뜯겨진 스티커와 변이 닿지 않은 (2, n-1)의 스티커를 뜯는다.

● 아무것도 뜯지 않는다. 이는 (2, n-2)의 스티커를 뜯기 위함이다.

단 두 가지라 함은 위의 두 가지 일 외에는 일어나지 않는다는 것을 뜻한다...

 

그런데 생각해보자

(1, n)의 스티커를 뜯었을 때 (2, n-1)의 스티커를 뜯을 경우, 왼쪽에서 부터 스티커를 뜯어서 (2, n-1)의 스티커를 뜯고! 점수가 최대가 되는 [최댓값으로의 길]은 분명히 존재할 것이다.

이 [최댓값으로의 길]로 얻어지는 스티커 점수의 합의 최댓값..

이 값은.. 과연 움직이지 않는 [사실]이라고 할 수 있을까?

 

다음과 같은 2x4 스티커가 있다고 하자.

[2x4 스티커]

100 10 20 30
 10 90 40 50

(1, 4)의 스티커(= 30)을 뜯었을 때 (2, 3)의 스티커(= 40)를 뜯을 경우 점수의 합을 최대로 만드는 [최댓값으로의 루-트]는

 

● 1열에서 1행의 스티커를 뜯기(= 100)

● 2열에서 스티커 뜯지 않기(= 0)

 

이며 점수의 합은 100 + 0 + 40 = 140이 된다.

이 140이라는 값은 (2, 3)의 스티커를 뜯어서 얻을 수 있는 스티커 점수의 [최댓값]이다(3열 까지).

 

이 값은 어떤 경우 어떤 상황이라도 절대 변하지 않는 [진실]이라 할 수 있다.

(1,4)의 스티커를 뜯든 뜯지 않든 뭘 하든

(2,3)의 스티커를 뜯었을 때 얻을 수 있는 최댓값인 이 140점이라는 [진실]은 절대로 변하지 않는다. 이는 스티커가 주어질 때부터 정해진 [운-명]인 것이다.

 

앞서 설명했던 것처럼 (1,4)의 스티커를 뜯었을 때 일어날 수 있는 일은 (2, 3)의 스티커를 뜯던가, 3열에서 스티커를 뜯지 않고 (2, 2)의 스티커를 뜯는 두 가지 일 이외에에는 일어나지 않는다.

 

[(2, 3)의 스티커를 뜯었을 때 얻을 수 있는 최댓값]과 [(2, 2)의 스티커를 뜯었을 때 얻을 수 있는 최댓값]은 반드시 존재하며, (1, 4)의 스티커를 뜯었을 때 일어날 수 있는 유일한 사건이다.

 

때문에 [(1,4) 스티커를 뜯었을 때 얻을 수 있는 점수의 최댓값]을 계산하기 위해서 각 열에서 스티커를 뜯을지 내버려둘지 일일이 판단할 필요 없이 이 두 값을 비교해서 더 큰 값에 (1,4) 스티커의 점수(=30)를 더하면 그 값이 바로 [(1,4) 스티커를 뜯었을 때 얻을 수 있는 점수의 최댓값]이 된다.

 

● (2, 3)의 스티커를 뜯었을 때 얻을 수 있는 점수의 최댓값은 앞의 계산에서 140

● (2, 2)의 스티커를 뜯었을 때 얻을 수 있는 점수의 최댓값은 190이 된다.

 

따라서 위의 예제의 경우 (1, 4)의 스티커를 뜯었을 때 얻을 수 있는 점수의 최댓값은

(2, 2)의 스티커를 뜯었을 때 얻을 수 있는 최댓값(= 190) + (1, 4) 스티커의 점수(= 30) = 210이 된다. 

 

 

이에 따라 문제를 풀기 위해 다음과 같은 수식을 정의할 수 있다.

 

2xi의 스티커가 있을 때 d[row][col]와 p[row][col]는,

 

● d[row][col] : row행 col열의 스티커를 뜯었을 때얻을 수 있는 점수의 최댓값(행은 0부터 세기로 한다.)

● p[row][col] : row행 col열의 스티커의 점수

 

를 의미한다고 하자.

 

그러면 다음과 같은 식이 성립한다.

[점화식]

d[0][i] = p[0][i] + max(d[1][i - 1], d[1][i - 2])
d[1][i] = p[1][i] + max(d[0][i - 1], d[0][i - 2])

 

2xi 스티커가 있을 때, 왼쪽부터 열부터 스티커를 뜯는다면 반드시 마지막 열의 1행(= 0, i) 또는 2행(= 1, i)의 스티커는 [뜯기게]된다.

 

따라서.. 최종적으로 우리가 "확인해야 할 것"은 d[0][i]와 d[1][i]의 값을 구하고 둘을 비교해서 더 큰 값을 찾는 것이다.

그것이 이 문제의 [답]이 될 것이다. 

 

 

 

 

■ 입력

[입력]

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int total = scanner.nextInt();

    for (int i = 0; i < total; i++) {   //[1]
        int n = scanner.nextInt();   //[2]
        int[][] p = new int[2][n + 1];
        int[][] d = new int[2][n + 1];

        for (int j = 0; j < 2; j++) {   //[3]
            Arrays.fill(d[j], -1);
        }

        for (int j = 0; j < 2; j++) {   //[4]
            for (int k = 1; k < n + 1; k++) {
                p[j][k] = scanner.nextInt();
            }
        }
        
		.
		.
		.
	}
}

● [1] : 전체 입력은 처음에 입력받은 테스트 케이스(= total)만큼 반복한다.

● [2] : 열의 길이를 입력받아 n에 저장하고 p와 d를 생성한다.

● [3] : 해당 스티커를 뜯었을 때 얻을 수 있는 최댓값을 저장할 d의 모든 값을 -1로 초기화한다.

※ dp를 구현한 메서드에서 d의 원소에 값이 있는지를 판단하기 위함. 0으로 하지 않는 이유는 최댓값이 0일 수도 있기 때문.

 

● [4] : 스티커의 점수 p를 입력받은 값으로 채운다.

 

 

 

■ 초기값 설정

[초기값 설정]

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();

        for (int i = 0; i < total; i++) {
			
			.
			.
			.
            
            d[0][1] = p[0][1];   //[1]
            d[1][1] = p[1][1];
            if (n >= 2) {   //[2]
                d[0][2] = p[0][2] + d[1][1];
                d[1][2] = p[1][2] + d[0][1];
			}
			.
			.
			.
           
		}
}

앞서 구한 d의 점화식에서는 2열 이하의 값을 계산할 수 없다.

즉, d[0][2]와 같은 값은 우변의 열이 0 이하가 되기 때문에 그 값을 구할 수 없다.

따라서 2열 이하의 d값은 초기에 세팅해주어야 한다.

 

● [1] : d[x][1]의 값은 첫 번째 열에서 스티커를 뜯을 때의 최댓값이므로 스티커의 점수 그 값 자체가 된다.

            d[x][1] = p[x][1]

 

● [2] : d[x][2]는 두 번째 열에서 스티커를 뜯었을 때 최댓값을 의미한다.

            만약 (0, 2)의 스티커를 뜯는다면 자동적으로 첫 번째 열에서 값을 최대로 하기 위해 할 수 있는 것은 변이 닿지 않은 (1,1)의 스티커

           를 뜯는 것 밖에 없다.

            d[0][2] = p[0][2] + p[1][1] = p[0][2] + d[1][1]

            d[1][2] = p[1][2] + p[0][1] = p[1][2] + d[0][1]

 

 

 

■ 출력, dp

[출력]

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int total = scanner.nextInt();

    for (int i = 0; i < total; i++) {
       
		.
		.
		.
        
        int result = Math.max(dp(0, n, p, d), dp(1, n, p, d));   //[1]
        System.out.println(result);   //[2]
    }
}

● [1] : dp 메서드로 d[0][n]과 d[1][n]의 값을 구하고 둘을 비교해서 더 큰 값을 문제의 답으로 결정한다.

● [2] : 결과가 담긴 result를 출력한다.

 

 

[dp]

public static int dp(int i, int j, int[][]p, int[][]d) {
    if (j == 1) {   //[1]
        return d[i][1];
    }
    if (j == 2) {
        return d[i][2];
    }
    if (d[i][j] != -1) {   //[2]
        return d[i][j];
    }

	//[3]
    d[i][j] = p[i][j] + Math.max(dp(1 - i, j - 1, p, d), dp(1 - i, j - 2, p, d));   

    return d[i][j];
}

● dp 메서드는 i와 j 값을 받아 i행 j열의 스티커를 뜯었을 때 얻을 수 있는 최댓값인 d[i][j]를 계산하고 반환하는 메서드이다.

● [1] : 초기값이 정해진 1열이나 2열의 값은 바로 반환할 수 있기 때문에 j에 1 또는 2가 들어오면 바로 값을 반환한다.

● [2] : 만약 d[i][j]의 값이 이미 계산되어있다면 그 값을 바로 반환한다.

● [3] : 앞서 구한 점화식을 사용해서 d[i][j]의 값을 구한다. 점화식에 사용될 d의 값들은 dp메서드를 재귀적으로 호출해서 구해진다.

 

 

 

■ 전체 코-드

[전체 코-드]

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int dp(int i, int j, int[][]p, int[][]d) {
        if (j == 1) {
            return d[i][1];
        }
        if (j == 2) {
            return d[i][2];
        }
        if (d[i][j] != -1) {
            return d[i][j];
        }

        d[i][j] = p[i][j] + Math.max(dp(1 - i, j - 1, p, d), dp(1 - i, j - 2, p, d));

        return d[i][j];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();

        for (int i = 0; i < total; i++) {
            int n = scanner.nextInt();
            int[][] p = new int[2][n + 1];
            int[][] d = new int[2][n + 1];

            for (int j = 0; j < 2; j++) {
                Arrays.fill(d[j], -1);
            }

            for (int j = 0; j < 2; j++) {
                for (int k = 1; k < n + 1; k++) {
                    p[j][k] = scanner.nextInt();
                }
            }

            d[0][1] = p[0][1];
            d[1][1] = p[1][1];
            if (n >= 2) {
                d[0][2] = p[0][2] + d[1][1];
                d[1][2] = p[1][2] + d[0][1];
            }

            int result = Math.max(dp(0, n, p, d), dp(1, n, p, d));
            System.out.println(result);
        }

    }
}