DP - 9465 (스티커)

 

9465번: 스티커 (acmicpc.net)

9465번: 스티커

 

 

스티커 문제입니다. 2열로 제한 되어 있기 때문에 일정한 패턴을 보였습니다.

O	X
X	ㅁ	ㅁ

위와 같이 왼쪽 위의 스티커를 떼어낸다면 다음 스티커는 아래열의 대각선 혹은 대각선 오른쪽의 스티커 둘 중 하나를 떼어내어야만 최대 점수를 가질 수 있는 스티커를 떼어낼 수 있습니다. 이후 스티커를 하나씩 떼어낼때 마다 열을 바꾸어가면서 스티커를 떼어내야 합니다. 

 

이 조건을 가지고 코드를 구현한다면 다음과 같이 나오게 됩니다. 

 

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


public class Main {




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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int t = Integer.parseInt(br.readLine());

        for(int i = 0; i<t; i++){// 테스트 케이스 시도 횟수
            int num = Integer.parseInt(br.readLine());
            int number[][] = new int[2][num+1]; // 원본 배열
            int score[][] = new int[2][num+1]; // 점수를 저장할 배열


            for(int k = 0; k<2; k++){
                st = new StringTokenizer(br.readLine());
                for(int j =1; j<=num; j++){
                    number[k][j] = Integer.parseInt(st.nextToken());
                }
            }

            score[0][1] = number[0][1];
            score[1][1] = number[1][1];

            for (int j = 2; j<=num; j++){
                score[0][j] = number[0][j] + Math.max(score[1][j-1] , score[1][j-2]);
                score[1][j] = number[1][j] + Math.max(score[0][j-1] , score[0][j-2]);
            }

            System.out.println(Math.max(score[0][num], score[1][num]));
        }

    }
}

 

부족했던 점

처음에는 생각이 않아서 다른 코드에서 힌트를 얻어서 풀었습니다. 열이 지속적으로 바뀌고 대각선 왼쪽 혹은 대각선 방향에서의 최대값중 하나라고 생각하였는데 이때, 값을 갱신하기 위해서 점수들의 합을 갱신할 배열의 크기를 각각 1을 더해주어서 점화식이 성립하도록 해주었습니다. 

 

이외에도 Scanner 가 아닌 BufferedReader가 처리속도가 더 빠르기 때문에 이 문제를 기점으로 Scanner 사용은 최대한 자제하려고 합니다.