[알고리즘] 백준 9465 스티커 -dp- 자바

 

www.acmicpc.net/problem/9465

9465번: 스티커

 

 

 

처음 완전탐색으로 접근했다가 삽질만 했습니다. 제출 시 60초가 걸리는 테스트케이스와 100,000개의 n 때문에 완전탐색으로 푼다고 해도 시간초과가 날 것 같당..

 

이후 서칭 후 DP 문제인 것을 알고 dp로 풀었습니다. 다음 그림으로 점화식을 세우면 됩니다.

 

[Java]

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int[][] arr = new int[2][n + 1];
            int[][] dp = new int[2][n + 1];
            for (int j = 0; j < 2; j++) { //초기화
                for (int k = 1; k <= n; k++) {
                    arr[j][k] = sc.nextInt();
                }
            }
            dp[0][1] = arr[0][1];
            dp[1][1] = arr[1][1];
            for (int a = 2; a <= n; a++) {
                dp[0][a] = Math.max(dp[1][a - 1], dp[1][a - 2]) + arr[0][a];
                dp[1][a] = Math.max(dp[0][a - 1], dp[0][a - 2]) + arr[1][a];
            }
            System.out.println(Math.max(dp[0][n], dp[1][n]));
        }
    }
}

 

 

 

 

 

 

 

 

 

 

 

풀이 방법을 잘 설명해놓으셔서 링크남깁니다.

fbtmdwhd33.tistory.com/76

[백준,BOJ 9465] 스티커( JAVA 구현)

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!