[BOJ-Silver1] 9465번 스티커

💡 풀이

• n번째 스티커 중 윗칸(첫번째 행)을 떼려면 => n-1번째 스티커 중 아래칸(두번째 행)을 떼거나 떼지 않는 경우 중 최대값
• dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + score[0][i]
  dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + score[1][i]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
		for(int k = 0; k<T; k++){
			int n = Integer.parseInt(br.readLine());
            
            // 스티커 점수 배열에 넣기
			int[][] score = new int[2][n + 1];
			for (int j = 0; j <= 1; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int i = 1; i <= n; i++) {
					score[j][i] = Integer.parseInt(st.nextToken());
				}
			}

			int[][] dp = new int[2][n + 1];
			dp[0][1] = score[0][1];
			dp[1][1] = score[1][1];
			for(int i = 2; i<=n; i++){
				dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + score[0][i];
				dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + score[1][i];
			}

			System.out.println(Math.max(dp[0][n], dp[1][n]));
		}
	}
}

💡 첫번째 풀이

• 스티커를 떼지 않는 경우를 행에 추가 (더 복잡함 😓)
• 스티커를 떼지 않을 때(dp[0][n])는 직전 스티커의 점수가 모두 들어갈 수 있어서 3개 비교
• dp[0][i] = Math.max(dp[0][i-1], Math.max(dp[1][i-1], dp[2][i-1]));
  dp[1][i] = Math.max(dp[0][i-1], dp[2][i-1]) + score[1][i];
  dp[2][i] = Math.max(dp[0][i-1], dp[1][i-1]) + score[2][i];

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
		for(int k = 0; k<T; k++){
			int n = Integer.parseInt(br.readLine());
			int[][] score = new int[3][n + 1];

			for (int j = 1; j <= 2; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int i = 1; i <= n; i++) {
					score[j][i] = Integer.parseInt(st.nextToken());
				}
			}

			int[][] dp = new int[3][n + 1];
			dp[0][1] = 0;
			dp[1][1] = score[1][1];
			dp[2][1] = score[2][1];
			for(int i = 2; i<=n; i++){
				dp[0][i] = Math.max(dp[0][i-1], Math.max(dp[1][i-1], dp[2][i-1]));
				dp[1][i] = Math.max(dp[0][i-1], dp[2][i-1]) + score[1][i];
				dp[2][i] = Math.max(dp[0][i-1], dp[1][i-1]) + score[2][i];
			}

			int result = Math.max(dp[0][n], Math.max(dp[1][n], dp[2][n]));
			System.out.println(result);
		}
	}
}