[백준] 9465: 스티커

문제

문제 풀이

예를 들어 cost[0][1]에서 가는 방법에 대해 생각해보았다.

cost[0][1] = 50 에서 갈 수 있는 곳은 cost[1][2] = 50과 cost[1][3]이다.
dp[0][1] = Math.math(dp[1][2], dp[1][3]) + cost[0][1] 을 통해서, 둘 중 어느 곳으로 가는지 결정할 수 있다.

cost[0][3]으로 가는 것을 고려하지 않는 이유는 dp[1][2]에서 가야하는 곳을 선택할 때 고려하기 때문이다.

이를 통해 다음과 같은 규칙을 얻었다.
dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + cost[0][j]
dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + cost[1][j]

Math.max(dp[0][n], dp[1][n])

코드

package DP;

import java.util.Scanner;

public class ANS9465 {

    static int dp[][], cost[][];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        //테스트 케이스
        int t = sc.nextInt();

        for(int i = 0 ; i < t ; i++){
            //테스트 케이스 별 n을 입력받는다.
            int n = sc.nextInt();

            //입력된 n에 따라 배열을 선언
            dp = new int[2][n+1];
            cost = new int[2][n+1];

            //2*n의 비용을 입력받는다.
            for(int j = 0 ; j < 2 ; j++){
                for(int k = 1 ; k <= n ; k++){
                    cost[j][k] = sc.nextInt();
                }
            }

            //dp초기화
            dp[0][1] = cost[0][1];
            dp[1][1] = cost[1][1];

	    //최댓값 구하기
            for(int m = 2 ; m <= n ; m++){
                dp[0][m] = Math.max(dp[1][m-1], dp[1][m-2]) + cost[0][m];
                dp[1][m] = Math.max(dp[0][m-1], dp[0][m-2]) + cost[1][m];
            }
		
            System.out.println(Math.max(dp[0][n], dp[1][n]));
        }
    }


}

---

이제 어느정도,, dp에 대해 안다고 자만하는 이순간
2시간 동안 해매는 나를 보며 자만하지 말자고 다짐한 오늘
처음엔 가장 큰 수부터 나열해서 찾아가는 방식을 택했지만, 역시 아니었다

아직은 연습이 더 필요한가보다ㅎㅎ!!