백준 9465번: 스티커

문제 설명

• https://www.acmicpc.net/problem/9465
• 스티커의 점수를 최대한으로 구해야 합니다. 단, 인접한 스티커를 선택하는 건 불가능합니다.

접근법

• DP라는 걸 파악할 수 있어야 합니다.
• 저는 거꾸로 생각했습니다. 0행i열 스티커를 선택했을 때
  • 0행i-1열스티커는 선택이 불가능 합니다.
  • 1행i-1열스티커는 선택이 가능합니다.
  • 0행i-2열, 1행i-2열스티커는 선택이 가능합니다.
  • i-3열부터는 i-1스티커의 선택에 포함되기 때문에 선택하지 않습니다.

정답

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			int N = sc.nextInt();
			int[][] arr = new int[2][N + 1];
			for (int i = 0; i < 2; i++) {
				for (int j = 1; j <= N; j++) {
					arr[i][j] = sc.nextInt();
				}
			}

			for (int i = 2; i <= N; i++) {
				arr[0][i] += Math.max(Math.max(arr[1][i - 1], arr[0][i - 2]), arr[1][i - 2]);
				arr[1][i] += Math.max(Math.max(arr[0][i - 1], arr[0][i - 2]), arr[1][i - 2]);
			}
			System.out.println(Math.max(arr[0][N], arr[1][N]));

		}
	}

}

기타

• Scanner가 아닌 BufferedReader를 사용하면 시간과 메모리를 단축시킬 수 있습니다.