백준 9465 스티커 Java

정답률 47퍼센트 dp문제인 스티커이다.

난 어려웠는데 정답률이 꽤 높은걸 보면 잘하는 사람들이 참 많구나 싶다.

 

이 문제는 이렇게 풀어야 한다고 한다.

스티커가 올 수 있는 경우에 수에 따라 dp[n][]배열을 만들어 준다.

 

첫 번째 경우인 dp[n][0]은 

X

X

두 개 다 때지 않은 경우

 

두 번째 경우인 dp[n][1]은

O

X

위쪽을 땐 경우

 

세 번째 경우인 dp[n][2]는

X

O

아래쪽을 땐 경우이다.

 

이렇게 해서 점화식을 생각해내면 된다..

첫 번째 경우엔 둘 다 때지 않았기 때문에 n-1에 세가지 경우가 모두 와도 상관이 없으므로

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

두 번째 경우엔 위쪽을 땠기 때문에 n-1에서 위쪽을 땐 경우는 올 수 없다.

또 스티커 점수도 더해준다. 위쪽을 땐 경우이기 때문에 n열의 0번째 행의 점수를 추가한다.

dp[n][1] = Math.max(dp[n-1][0], dp[n-1][2])+ 스티커[0][n];

세 번째 경우도 마찬가지로 해주면 된다. 아래쪽을 땐 경우니까

dp[n][2] = Math.max(dp[n-1][0], dp[n-1][1])+ 스티커[0][n];

 

답을 구할때는 dp[n]에서 가장 큰수를 구하면 된다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int tc = scan.nextInt();
        
        for(int t=0; t<tc; t++) {
            int n = scan.nextInt();
            int [][] a = new int[2][n+1];
            int [][] dp = new int[n+1][3];
 
            for(int i=0; i<2; i++)
                for(int j=1; j<=n; j++)
                    a[i][j] = scan.nextInt();
            
            dp[1][0] = 0; //X X
            dp[1][1] = a[0][1]; //O X
            dp[1][2] = a[1][1]; //X O
            
            for(int i=2; i<=n; i++) {
                dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][2]));
                dp[i][1] = Math.max(dp[i-1][0], dp[i-1][2])+a[0][i];
                dp[i][2] = Math.max(dp[i-1][0], dp[i-1][1])+a[1][i];
            }
                    
            System.out.println(Math.max(dp[n][0], Math.max(dp[n][1], dp[n][2])));
        }
    }

 

이런 점화식을 생각해내는 분들은 대단하다. 난 못했다.