백준 9465 풀이
https://www.acmicpc.net/problem/9465
스티커
문제의 조건은 다음과 같다.
- 떼어낸 스티커의 상하좌우의 스티커를 이어서 뗄 수 없다.
- 떼어낸 스티커의 점수의 총합이 최대가 되어야 한다.
떼어낸 스티커의 상하좌우를 연달아 뗄 수 없다면 일반적으로 한칸씩 건너 떼는 것을 생가할 것이다.
그런데 문제에 주어진 스티커의 배열은 2차원이기 때문에 대각선도 고려할 수 있다.
문제의 예시에서 50을 떼어냈다고 하면 다음으로 떼어낼 곳은 한칸 앞 대각선인 50과 두칸 앞 대각선인 70일 것이다.
물론 두칸 옆인 100도 가능은 하다. 하지만 점수를 최대로 얻을려면 대각선으로 내려가 2차원 형태를 최대한 활용해야한다.
아무튼 50을 처음에 떼어냈다면 다음 스티커를 떼어냄으로 얻을 수 있는 점수느 50+50 또는 50+70이 될 것이다. (1,1)의 값은 100이 되고 (1,2)의 값은 120이 된다.
그렇다면 (1,i)의 값은 어떻게 될까?
(1,2)의 값 120 같은 경우 어떻게 볼 수 있냐면, 한칸 뒤 대각선 점수 + 자신의 점수 또는 두칸 뒤 대각선 점수 + 자신의 점수가 될 수 있다.
둘 중 큰 값을 선택하겠지만...
즉, 점화식이
dp[1][i] = Max(dp[0][i-1], dp[0][i-2])
가 된다.
dp[0][i]도 마찬가지로 위치만 바꿔주면 된다.
끝!!
import java.io.*;
public class Main {
/*static int count = -1;
static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
static int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};*/
//static boolean visited[];
static int n, s;
static int nums[];
static int count = 0;
static int mask[];
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
String num = br.readLine();
n = Integer.parseInt(num);
// n+1로 선언한 이유는 배열 탐색 과정에서 i-2에서 인덱스 범위 초과 문제를 막기 위해서
int[][] arr = new int[2][n + 1];
int[][] dp = new int[2][n + 1];
for (int k = 0; k < 2; k++) {
String[] tmp = br.readLine().split(" ");
for (int l = 0; l < tmp.length; l++) {
arr[k][l + 1] = Integer.parseInt(tmp[l]);
}
}
dp[0][1] = arr[0][1];
dp[1][1] = arr[1][1];
for (int j = 2; j <= n; j++) {
dp[0][j] = Math.max(dp[1][j-2], dp[1][j-1]) + arr[0][j];
dp[1][j] = Math.max(dp[0][j-2], dp[0][j-1]) + arr[1][j];
}
int ans = Math.max(dp[0][n], dp[1][n]);
bw.write(ans+"\n");
}
br.close();
bw.close();
}
}
Author And Source
이 문제에 관하여(백준 9465 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-9465-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)