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

-내 생각

  이 문제 역시 내 힘으로 풀 수는 없었다..  처음 생각했던 것은 각 스티커를 붙였을 때와 붙이지 않았을 때를 고려해 각각의 경우의 수에 따라 최댓값을 찾으려 했었는데, 해결하지 못해서 다른 분들의 글을 확인해 보니 고려하지 않은 부분이 있었다. 아직 한참 모자란 것 같다.

 

-해법

  우선 하나의 스티커를 기준으로 가능한 경우의 수를 보자. 스티커를 하나 선택하면 해당 스티커를 기준으로 상하좌우는 선택할 수 없다는 제한이 있다. 그렇다면 스티커를 하나 선택했을 때, 가능한 경우의 수는 대각선으로 가는 경우가 존재하는데, 이를 그림으로 표현해보면, 

 

  위와 같은 경로가 가능하다. 왜 10이나 60은 갈 수없냐고 할 수 있는데, 10 또는 60, 100으로 바로 갈 경우는 문제의 조건에 부합하지 않기 때문이다. 문제가 요구하는 것은 비용의 최댓값을 요구하는 것인데, 10으로 가는 경우는 50 -> 10으로 갈 경우 60이고, 50-> 50 -> 100 -> 10으로 갈 수도 있기 때문에, 60<210으로 바로 갈 수 있는 경우는 고려하지 않는 것이다. 60과 100 또한 마찬가지이다. (이 부분이 내가 처음에 고려하지 못한 부분이다.)  70의 경우에는 50을 선택하고 70을 선택하는 경우는 바로 50 -> 70의 경우 밖에 존재하지 않기 때문에 고려해야 한다. (대각선에 있는 50은 당연히 고려해야 한다.)

 

  이를 이용하여 점화식을 세워보면 특정 n번 째 dp값을 채우기 위해선, 한 칸 또는 두 칸 뒤의 대각선을 고려해주면 된다. 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]로 정의할 수 있다. 즉 예를 들어 70의 dp배열을 채우기 위해서는 70의 대각선 한 칸 뒤와 두 칸 뒤의 값 중 큰 값과 자신의 값을 더하면 된다. 왜냐하면 위에서 설명했듯이, 70으로 갈 수 있는 경우는 50 -> 70으로 바로 가는 경우와, 30 -> 10 -> 70으로 가는 경우가 있기 때문이다. 이는 Math.max(50 + 70 , 30 + 10 +70)이므로 50 -> 70의 경로가 선택되는 것이다.

import java.util.*;
import java.math.*;
public class Main {
	
	static int dp[][] , cost[][] ; // dp와 비용이 저장 될 배열
	
	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();
			
            //입력되는 n값에 따라 배열을 선언
			cost = new int[2][n+1];
			dp = new int[2][n+1];
			
			
			for(int j=0;j<2;j++) { // 비용을 입력
				for(int k=1;k<=n;k++) {
					cost[j][k] = sc.nextInt();
				}
			}
			
            // 0번째, 1번째 행의 첫 번째 열이 초기화로 초기값이 된다.
			dp[0][1] = cost[0][1];
			dp[1][1] = cost[1][1];
			
			
				for(int k=2;k<=n;k++) { // 열 반복만을 통해 0번과 1번행을 동시 처리
					dp[0][k] = Math.max( dp[1][k-1], dp[1][k-2])+cost[0][k];
					dp[1][k] = Math.max(dp[0][k-1],dp[0][k-2])+cost[1][k];
				}
				
				
				System.out.println(Math.max(dp[0][n], dp[1][n])); // n번 째 열의 최댓값을 반환 후 출력
			
		}
		
	}
	
}