[BOJ] 9465번: 스티커

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

9465번: 스티커

 

문제

 

입력

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

 

출력

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

 

난이도

실버 1

 

Sol

DP(점화식) - 각 열의 두 번째 스티커부터 대각선 방향의 한 칸 앞, 두 칸 앞의 스티커 중 점수가 높은 스티커를 선택해 더해나간다. dp 배열 각 열의 마지막 행은 해당 스티커를 선택했을 때 얻을 수 있는 점수의 최댓값이 된다. 두 행 중 최댓값을 찾아 출력.

public class B9465_스티커 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine());

        for(int i=0; i<T; i++){
            int n = Integer.parseInt(bf.readLine());

            int[][] stickers = new int[2][n+1]; // 노드의 이전 노드와 그 이전 노드를 고려하기 위해 n+1으로 크기 설정
            int[][] dp = new int[2][n+1];

            for(int j=0; j<2; j++){
                String[] input = bf.readLine().split(" ");
                // StringTokenizer -> String.split()으로 고치면서 시간은 줄고 메모리는 늘었다

                for(int k=1; k<n+1; k++) stickers[j][k] = Integer.parseInt(input[k-1]);
            }
            // input

            dp[0][1] = stickers[0][1];
            dp[1][1] = stickers[1][1];
            // 초기값 설정

            for(int j=2; j<n+1; j++){
                dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + stickers[0][j];
                dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + stickers[1][j];
            } // 대각선 방향의 한 칸 앞, 두 칸 앞의 스티커 고려
            // operation

            System.out.println(Math.max(dp[0][n], dp[1][n]));
            // 각 열의 마지막 스티커까지 확인한 후 최댓값을 출력
            // output
        }
    }
}

 

🙄

• 입력단에서 StringTokenizer를 String.split()으로 수정하면서 실행 시간은 줄어들고 필요 메모리는 증가했다
• stickers, dp 배열의 크기(n+1) 주의!

 

다이나믹 프로그래밍 문제는 왠지 풀 때마다 새로운 느낌이고, 점화식 세우는 게 어렵다.. 많이 풀어서 얼른 DP에 익숙해졌으면 좋겠다