문제 :
https://www.acmicpc.net/problem/9465
접근 :
- 위쪽을 뜯는 경우와 아래쪽을 뜯는 경우를 나눠서 생각한다.
- 가로의 위치가 0 과 1 인 경우에는 나올 수 있는 최대값을 dp에 저장한다.
- 가로의 위치가 2 이상인 경우에는 위쪽과 아래쪽을 나눠서 현재 위치까지 도달했을 때, 가능한 최대값을 dp에 저장한다.
- 가로로 진행할 때, 항상 위쪽과 아래쪽을 나누어 더 큰 값으로 ans 값을 갱신한다.
- n-1 까지 진행한 후, ans 값을 출력한다.
코드구현 :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for (int i=0 ; i < t ; i++) {
int n = Integer.parseInt(br.readLine());
int [][] map = new int[2][n];
long [][] dp = new long[2][n];
long ans = 0;
for(int j = 0 ; j < 2 ; j++){
String[] temp = br.readLine().split(" ");
for (int k = 0; k < n; k++) map[j][k] = Integer.parseInt(temp[k]);
}
dp[0][0] = map[0][0];
dp[1][0] = map[1][0];
ans = Math.max(ans, Math.max(dp[0][0], dp[1][0]));
if(n == 1) {
sb.append(String.format("%d %n", ans));
continue;
}
dp[0][1] = dp[1][0] + map[0][1];
dp[1][1] = dp[0][0] + map[1][1];
ans = Math.max(ans, Math.max(dp[0][1], dp[1][1]));
for(int j = 2 ; j < n ; j++){
dp[0][j] = Math.max(dp[1][j-2], dp[1][j-1]) + map[0][j];
dp[1][j] = Math.max(dp[0][j-2], dp[0][j-1]) + map[1][j];
ans = Math.max(ans, Math.max(dp[0][j], dp[1][j]));
}
sb.append(String.format("%d %n", ans));
}
System.out.println(sb);
br.close();
}
}
'JAVA > Coding Test' 카테고리의 다른 글
[JAVA] 프로그래머스 단속카메라_최소힙 (0) | 2024.06.27 |
---|---|
[JAVA] 백준 2688 줄어들지 않아_DP (0) | 2024.06.26 |
[JAVA] 백준 1520 내리막길_DP (0) | 2024.06.25 |
[JAVA] 백준 2193 이친수_DP (0) | 2024.06.24 |
[JAVA] 백준 2156 포도주_DP (0) | 2024.06.24 |