백준 9465 스티커(JAVA)

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

9465번: 스티커

 

 

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_BJ_9465_스티커 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        for(int tc=0; tc<t; tc++){
           int n = Integer.parseInt(br.readLine());
           int[][] sticker = new int[2][n];
           int[][] dp = new int[2][n+1];
           for(int i=0; i<2; i++){
               st = new StringTokenizer(br.readLine());
               for(int j=0; j<n; j++){
                   sticker[i][j] = Integer.parseInt(st.nextToken());
               }
           }

           int max;
           dp[0][1] = sticker[0][0];
           dp[1][1] = sticker[1][0];
           for(int i=2; i<=n; i++){
               dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + sticker[0][i-1];
               dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + sticker[1][i-1];
           }
           max = Math.max(dp[0][n], dp[1][n]);
           System.out.println(max);
        }//test case
    }//main

}

처음에는 완탐인줄 알고 pq이용해서 풀다가 도저히 안 될것 같아서 찾아봤다.

dp더라;;ㅎㅎ

 

이 문제는 결국 대각선을 봐야한다.

0번째 행이면, 1번째 행의 i-1열과 i-2열까지의 dp중에서 가장 큰 값을,

1번째 행이면, 0번째 행의 i-1열과 i-2열까지의 dp중에서 가장 큰 값을 택해서 스티커의 현재 위치와 더해주면 된다.

 

따라서 점화식을 세우면, 아래와 같다.

dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + sticker[0][i-1];
dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + sticker[1][i-1];

dp문제 다른 것 풀어봐야지...

 

 

참고한 블로그

https://propercoding.tistory.com/14

[백준] 9465번 : 스티커 – JAVA [자바]