[백준]9465번 스티커

2n 개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

9465번: 스티커

문제 풀이 ( 다른 사람 풀이 참고 )

이런건 보통 dp 였던 기억이 있는데 방향을 잡지 못했다.

bottom - up 방식으로 풀이하려고 하니, 다음 인접한 칸들에 대한 영향을 고려하기가 어려웠다.

따라서 다른 사람 풀이를 보았다.

• 규칙을 찾아야 했다. 무엇보다도. (r,c) 의 스티커를 뗄 수 있는 경우에 대한 최대값 를 찾는 방식으로 진행해야 했다.
  • 왼쪽에서부터 오른쪽으로 채워나가는 방식을 할 수 있었다.
  • 마지막에는, 가장 오른쪽 열 dp[0][n],dp[1][n] 중의 최댓값이 정답이 되게 된다.
• 이 때, board 를 따로 두어 각 칸의 스티커 값들을 저장해 두지 않아도 된다는 점이 새로웠다.

[백준 9465번] 스티커 Java 풀이

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

public class Main {
	public static int n;
	public static int[][] dp = new int[2][100001];

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StringTokenizer st1;
	public static StringTokenizer st2;

	public static void solve() throws IOException {
		st1 = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(st1.nextToken()); // 테스트 케이스 개수

		for (int i = 0; i < t; i++) {
			n = Integer.parseInt(br.readLine());
			st1 = new StringTokenizer(br.readLine()); // 보드의 첫 번째 줄에 대한 StringTokenizer
			st2 = new StringTokenizer(br.readLine()); // 보드의 두 번째 줄에 대한 StringTokenizer

			dp[0][1] = Integer.parseInt(st1.nextToken());
			dp[1][1] = Integer.parseInt(st2.nextToken());

			for (int c = 2; c <= n; c++) {
				dp[0][c] = Math.max(dp[1][c-1],dp[1][c-2]) + Integer.parseInt(st1.nextToken());
				dp[1][c] = Math.max(dp[0][c-1],dp[0][c-2]) + Integer.parseInt(st2.nextToken());
			}
			System.out.println(Math.max(dp[0][n], dp[1][n]));
		}

	}

	public static void main(String[] args) throws IOException {
		solve();
	}
}