[ 백준 9465 ] 스티커

1. 문제 링크 https://www.acmicpc.net/problem/9465

9465번: 스티커

2. 문제

3. 문제 요약

이차원 배열로부터 주어진 조건을 만족하는 최대값을 찾는 문제.

 

4. 문제 풀이

전형적인 DP 문제이다.

현재 상태에서 최대값을 얻기 위해서 고려해야할 이전 상태들을 파악하고,

현재 상태를 만들 수 있는 값들을 비교하여 비교 값의 최대값을 이용하여 탐색한다.

 

문제의 크기를 작게 축소해서 2x3 을 만들어보면, 경우의 수를 쉽게 구할 수 있다.

현재 상태(i)에서의 최대값을 구하는데 필요한 것이 직전의 두개 상태 (i-1), (i-2)만 고려하면 된다.

 

참고하는데 필요한 상태는 3개인데, 주어진 입력 조건에서 n>1 이므로,

예외를 만들고 싶지 않아서 DP 배열의 크기는 n+2로 설정해두고 계산했다.

5. 풀이 코드

public static int problem9465() throws Exception {
    str1 = new StringTokenizer(bfr.readLine());
    int n = Integer.parseInt(str1.nextToken());
    int[][] dp = new int[n + 2][2];
 
    str1 = new StringTokenizer(bfr.readLine());
    str2 = new StringTokenizer(bfr.readLine());
    for (int i = 2; i < n + 2; i++) {
        dp[i][0] = Integer.parseInt(str1.nextToken()) + Math.max(dp[i - 1][1], dp[i - 2][1]);
        dp[i][1] = Integer.parseInt(str2.nextToken()) + Math.max(dp[i - 1][0], dp[i - 2][0]);
    }
    return  Math.max(dp[n + 1][0], dp[n + 1][1]);
}