9465

스티커 문제

 

 

아래 사이트를 참조함.

https://fbtmdwhd33.tistory.com/76

 

점화식을 얻기 위한 아이디어를 떠올리는게 문제구나...

 

2xN 의 입력

가운데 녀석을 제거하면 상하좌우에 있는 요소는 사용 불가
점수의 합이 최대가 되도록 스티커를 뗀다.
 
50 10 100 20 40
30 50 70 10 60

dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + S[0][j];
dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + S[1][j];

 

import java.util.Scanner;

class Main {

	static int N;
	static int[][] S;
	static int[][] dp;

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		int answer = 0;
		for (int t = 0; t < T; ++t) {
			N = in.nextInt();
			S = new int[2][N + 1];
			dp = new int[2][N + 1];

			// dp를 S의 값으로 초기화
			for (int i = 0; i < 2; ++i) {
				for (int j = 1; j <= N; ++j) {
					S[i][j] = in.nextInt();
				}
			}

			// 1번 인덱스 까지 초기화
			dp[0][1] = S[0][1];
			dp[1][1] = S[1][1];

			for (int j = 2; j <= N; ++j) {
				// 자기 자신과 대각선 뒷쪽의 두개의 값 중, 큰것을 선택하여 저장.
				dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + S[0][j];
				dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + S[1][j];
			}
			answer = Math.max(dp[0][N], dp[1][N]);

			System.out.println(answer);
		}
	}

}

 

 

백준_9465_스티커.xlsx

0.01MB