[Java] BOJ 9465번 스티커

9465번: 스티커

---

풀이

처음 스티커를 선택하는 경우는 각각의 스티커를 가져오게 했습니다.

그다음으로 이전 스티커를 선택했다면 이전에 뗄 수 있는 스티커까지 즉, 만약 현재 스티커의 i가 0이라면 memo[1][i - 1]을 i가 1이라면 memo[0][i - 1]의 값을 가져오게 했습니다.

마지막으로 이전 스티커를 선택하지 않는 경우에는 그 이전까지 뗄 수 있는 스티커까지 즉, memo[0][j - 2], memo[0][j - 1] 중 큰 값을 가져와 이전 스티커를 선택한 경우와 비교하여 최댓값을 구해 현재 스티커의 값을 더해주어 해결했습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int T, n;
	public static int[][] stickers;
	public static int[][] memo;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = Integer.parseInt(br.readLine());
		
		for (int tc = 0; tc < T; ++tc) {
			n = Integer.parseInt(br.readLine());
			
			stickers = new int[2][n + 1];
			memo = new int[2][n + 1];
			
			for (int i = 0; i < 2; ++i) {
				st = new StringTokenizer(br.readLine(), " ");
				
				for (int j = 1; j <= n; ++j) {
					stickers[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			memo[0][1] = stickers[0][1];
			memo[1][1] = stickers[1][1];
			for (int i = 2; i <= n; ++i) {
				memo[0][i] = Math.max(memo[1][i - 1], Math.max(memo[0][i - 2], memo[1][i - 2])) + stickers[0][i];
				memo[1][i] = Math.max(memo[0][i - 1], Math.max(memo[0][i - 2], memo[1][i - 2])) + stickers[1][i];
			}
			
			System.out.println((memo[0][n] < memo[1][n]) ? memo[1][n] : memo[0][n]);
		}
	}
}

---

pyo7410/Algorithm