백준 [9465] 스티커

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

9465번: 스티커

 

풀이

 

점수가 최대가 되도록 하면서 두 변을 공유하지 않는 집합의 합을 구하는 것이 핵심인 문제였다.

 

첫번째 열부터 마지막 열까지 탐색해 나가면서 두 변을 공유하지 않는 가장 점수가 큰 집합을 찾아야 했다.

 

첫 번째 열과 두 번째 열의 경우를 보면

첫 번째 열은 비교 대상이 자기 자신 밖에 없다. (pass)

두 번째 열은 비교 대상이 두 변을 공유하지 않는 바로 이전의 열의 대각 성분이 있다. 그래서 각 위치의 대각 성분을 더한 값이 집합의 최대 점수가 된다.

 

세 번째 열부터는 경우의 수가 3개가 있다.

1. 바로 이전 열의 대각 성분 (파란색)
2. 같은 열의 두 칸 뒤의 성분 (빨간색)
3. 같은 열의 두 칸 뒤 대각 성분(연두색)

 

이 3가지 경우 중 해당 위치의 성분과 더했을 때가 가장 큰 값이 가장 큰 집합을 고른 경우가 된다.

 

그다음 이를 마지막 열까지 진행한 다음 마지막 행의 값 중 더 큰 값이 서로 변을 공유하지 않으면서 가장 큰 점수의 집합이 된다.

 

 

 

정답 코드

package com.baekjoon.p9465;

import java.io.*;
import java.util.*;

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

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

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

            int[][] arr = new int[2][N];

            for (int i = 0; i < 2; i++) {

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

            if (N > 1) {
                arr[0][1] += arr[1][0];
                arr[1][1] += arr[0][0];

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

            int result = Math.max(arr[0][N - 1], arr[1][N - 1]);

            sb.append(result + "\n");
        }

        System.out.println(sb);
    }
}