DP: 9465: 스티커 [JAVA]

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

 

---

 

 

 

문제 접근

 

 

 

 

https://chaechaepower.tistory.com/15

 

> 과거의 내가 아주 잘 정리해둠.

 

 

 

 

 

▲ 간과한 것 

 

 

- N을 키우면서 규칙을 찾을 것

 

- dp 배열 정의를 명확하게 세울 것

 

 

 

 

 

 

 

코드

 

 

top down - 재귀

 

 

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

public class Main {

	static Integer[][] dp;
	static int[][] arr;

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

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int testN = Integer.parseInt(bf.readLine());

		for (int i = 0; i < testN; i++) {

			int n = Integer.parseInt(bf.readLine());

			arr = new int[2][n];
			dp = new Integer[2][n];

			StringTokenizer st;

			for (int j = 0; j < 2; j++) { // arr[][] 초기화
				st = new StringTokenizer(bf.readLine());
				for (int k = 0; k < n; k++) {
					arr[j][k] = Integer.parseInt(st.nextToken());
				}
			}

			dp[0][0] = arr[0][0];
			dp[1][0] = arr[1][0];

			if (n >= 2) {
				dp[0][1] = arr[0][1] + arr[1][0];
				dp[1][1] = arr[1][1] + arr[0][0];
			}

			System.out.println(Math.max(recur(0, n - 1), recur(1, n - 1)));

		}

		bf.close();
	}

	static int recur(int i, int j) {

		if (dp[i][j] == null) {

			if (i == 0) {
				dp[i][j] = Math.max(recur(1, j - 1), recur(1, j - 2)) + arr[0][j];
			}
			if (i == 1) {
				dp[i][j] = Math.max(recur(0, j - 1), recur(0, j - 2)) + arr[1][j];
			}

		}

		return dp[i][j];
	}

}

 

 

 

 

 

 

 

bottom up - 반복문

 

 

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

public class Main {

	static Integer[][] dp;
	static int[][] arr;

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

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int testN = Integer.parseInt(bf.readLine());

		for (int i = 0; i < testN; i++) {

			int n = Integer.parseInt(bf.readLine());

			arr = new int[2][n];
			dp = new Integer[2][n];

			StringTokenizer st;

			for (int j = 0; j < 2; j++) { // arr[][] 초기화
				st = new StringTokenizer(bf.readLine());
				for (int k = 0; k < n; k++) {
					arr[j][k] = Integer.parseInt(st.nextToken());
				}
			}

			dp[0][0] = arr[0][0];
			dp[1][0] = arr[1][0];

			if (n >= 2) {
				dp[0][1] = arr[0][1] + arr[1][0];
				dp[1][1] = arr[1][1] + arr[0][0];
			}

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

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

		}

		bf.close();
	}

}