9465 스티커

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

예제 입력 1 두번째로 나온 값을 표현했다.

10에서 다음 번으로 이동할 때, 아래(20), 오른쪽(30)으로는 이동 못하고,

위 그림에서 나타낸 것처럼 40,30 만 고려하면 된다.

 

그 이유는 다음과 같다.

1. 10->10(위쪽 3번째 값) (이동)

10에서 10으로도 물론 이동가능할 것이다.

하지만, 10->10으로 바로 이동하는 것보다는,

10(윗쪽 첫번째) ->40(아래쪽 두번째) ->10(위쪽 세번째) 이 더 많은 점수를 얻게 된다.

그래서 고려하지 않는다.

 

2. 10->50(아래쪽 4번째 값) (이동)

10에서 50으로도 물론 바로 이동 가능하다.

하지만, 10->40->10->50 으로 이동하는 게 더 많은 점수를 얻게 된다.

그래서 고려하지 않는다.

 

그 외에 뒤에 있는 100,60,20,40,80 등으로 10에서 바로 이동하지 않는 이유 역시

위에서 설명한 이유들과 같다.

 

따라서 위 그림에서 표현한 것처럼

윗쪽 첫번째 10에서 아래쪽 40,30으로 이동하는 경우만 고려하면 되는 것이다. 

 

그래서, 아래 대각선 두개를 고려하면 되므로,

 

dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + sticker[0][i],
dp[1][i]=Math.max(dp[0][i-1], dp[0][i-2]) + sticker[1][i]

 

위 그림에서는 아래 오른쪽으로 이동하는 대각선을 표시했지만,

여기서는 계산의 편의를 위해

왼쪽 아래로 이동하는 대각선으로 고려한 것이다.

방향만 다를 뿐 결국 같다.

 

 

 

 

맨 처음에는 이렇게 되는데, 0 점의 스티커를 고려한다고 생각하면 된다.

  

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
	
	
	
	public static void main(String[] args) throws IOException {
	
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int k=0;k<T;k++) {
		int N = Integer.parseInt(br.readLine());
	
		int sticker [][] = new int[2][N+1] ;
		
		for(int j=0;j<2;j++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " " );
		for(int i=1; i<=N;i++) {
			sticker[j][i]= Integer.parseInt(st.nextToken());
		}
		}
		
		int dp [][] = new int [2][N+1];
		
		dp[0][1] = sticker[0][1];
		dp[1][1] = sticker[1][1];
		
		
		for(int i=2; i<=N; i++) {
		
				dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + sticker[0][i];
				dp[1][i]=Math.max(dp[0][i-1], dp[0][i-2]) + sticker[1][i];
			
		}
		sb.append(Math.max(dp[0][N], dp[1][N])).append("\n");
		}
		sb.setLength(sb.length() - 1);
		System.out.print(sb);
	}
}

 

 

마지막 부분에 sb.setLength(sb.length()-1) 을 한 이유는

맨 마지막에는 띄어쓰기(append("\n")) 한 것을 없애기 위해서다

 

 

그래야 이렇게 결과값이

290 다음에 띄어쓰기가 안 되서 나온다.

 

 

 

 

 

참고 자료 : 

https://fbtmdwhd33.tistory.com/76

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