백준 9465번 스티커 S1 - DP

상근 교수님 .. 잘 지내시죠?

 

코테 준비할수록 DP 점화식을 찾거나 규칙 찾는거에 약한듯해서 DP위주로 준비하게 된다.

그래프는 이제 좀 감 잡았나 싶네  껄꼴껄~ 소주 땡긴다

 

문제를 읽고 가능한 수를 먼저 떠올리는 습관을 들였다.

문제를 보면 한 스티커를 선택하면 상하좌우 모두 사용이 불가능하다.

따라서 연속적으로 사용할 수 없고, 지그재그로 사용하면 가장 많은 수의 스티커를 붙일 수 있다.

하나의 경우가 더있는데 

이런 경우도 존재했다.

어릴적 바둑배웠는데 '날일자' 日 생각나네

요로코롬이 날일자 ㅎㅎ;;

 

그러면 점화식을 세워준다. << 젤 어려운거

DP는 2차원으로 해주자, 위에 스티커를 떼는경우와 아래 스티커 떼는 경우가 존재하니.

초기에는 맨 왼쪽에 있는 스티커를 기준으로 최대값을 구해서 오류가 발생했었다.

시작이 위쪽인경우와 시작인 아래인 경우로 나눴는데 이상하게 답이 안나왔다..

 

// 맨 왼쪽을 상단을 선택하냐, 하단을 선택하냐
			// 중간에 건너띄우는 방법도 존재함을 고려
			dp[0][0] = arr[0][0];
			dp[1][0] = arr[1][0];
			dp[0][1] = dp[0][0] + arr[1][1];
			dp[1][1] = dp[1][0] + arr[1][0];
//			// 점화식
//			dp[0][2] = Math.max(dp[0][1] + arr[0][2], dp[0][0] + arr[1][2]);
//			dp[1][2] = Math.max(dp[1][1] + arr[1][2], dp[1][0] + arr[0][2]);

 

에잉 테케는 맞았는데

 

지금 생각해보면 

 

 

 

위 같은 상황이라면 DP[0][3] 은 70이지만 DP[0][4]는 130이 최대값이 된다.

결국 DP[0][4]에 DP[0][3]을 활용하지 못하게된다.

점화식에 오류가 있었고. 스티커를 뜯는 위치를 기준으로 바꿔주었다.

현재 뜯는 위치에서 전전과 전만 고려하면 되었다.

 

만약 내가 3번째 위쪽 스티커를 뗀다면 그 전 2번째 위쪽 스티커를 떼지 않았어야한다.

아래쪽이라면 그 전 아래쪽 스티커를 떼지 않았어야 한다.

 

왼쪽 -> 3번째 위쪽 스티커를 떼는 경우 오른쪽 -> 3번째 아래 스티커를 떼는 경우

 

 

노란색은 떼진 스티커 위치이다. 파란색은 뜯을 위치이다.

3번째 위 스티커를 떼는 경우는 2가지가 존재하고,

3번째 아래 스티커를 떼는 경우 역시 2가지가 존재한다.

 

위 스티커     >> DP[0][3] = DP[1][0] + arr[0][3]  또는  DP[1][2] + arr[0][3]  

아래 스티커 >> DP[1][3] = DP[0][0] + arr[1][3]  또는  DP[0][2] + arr[1][3]

으로 점화식을 세우면

 

for (int i = 2; i <= N; i++) {
	dp[0][i] = Math.max(dp[1][i - 2], dp[1][i - 1]) + arr[0][i];
	dp[1][i] = Math.max(dp[0][i - 2], dp[0][i - 1]) + arr[1][i];
}

 

 

 

import java.util.*;
 
public class Main { // 백준 11403번 경로 찾기 S1
    // dp로 해결 N+1로 시작하자.. 
    public static int N, answer;
    public static int[][] arr;
    public static int[][] dp;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            arr = new int[2][N+1];
            dp = new int[2][N+1];
 
            for (int i = 0; i < 2; i++) {
                for (int j = 1; j <= N; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }
 
            dp[0][1] = arr[0][1];
            dp[1][1] = arr[1][1];
//            // 점화식
//            dp[0][2] = Math.max(dp[1][0],dp[1][1]) + arr[0][2];
//            dp[1][2] = Math.max(dp[0][0],dp[0][1]) + arr[1][2];
            for (int i = 2; i <= N; i++) {
                dp[0][i] = Math.max(dp[1][i - 2], dp[1][i - 1]) + arr[0][i];
                dp[1][i] = Math.max(dp[0][i - 2], dp[0][i - 1]) + arr[1][i];
            }
 
            int answer = Math.max(dp[0][N], dp[1][N]);
            System.out.println(answer);
        }
    }
 
}

 

 

꾸꾸