π [λ°±μ€μκ³ λ¦¬μ¦ νμ΄] Q.9465 μ€ν°μ»€ λ¬Έμ νμ΄ - java
π λ¬Έμ
https://www.acmicpc.net/problem/9465
π μ κ·Όλ²
Q.9465 μ€ν°μ»€ λ¬Έμ μ λλ€.
2nκ°μ μ€ν°μ»€κ° μ£Όμ΄μ§λλ€. κ° μ€ν°μ»€ λ§λ€ μ μκ° λΆμ¬λμ΄ μ£Όμ΄μ§λλ°
μ€ν°μ»€ ν μ₯μ λΌλ©΄ ν΄λΉ μ€ν°μ»€μ λ³μ 곡μ νλ μ€ν°μ»€λ€μ λΌμ΄λΌ μ μκ² λ©λλ€.
μ΄λ μ€ν°μ»€λ₯Ό λΌμ΄λ΄μ΄ κ°μ₯ λκ² λ°μ μ μλ μ μλ₯Ό ꡬνλ κ²μ΄ μ΄ λ¬Έμ μ λ΅μ λλ€.
λμ νλ‘κ·Έλλ°μ ν΅ν΄ νμ΄κ° κ°λ₯ν©λλ€.
μΈκ°μ§μ κ²½μ°κ° μμ΅λλ€.
νμ¬ μ€ν°μ»€λ₯Ό λΌμ§ μλ κ²½μ°μλ λ€μ μΉΈμ μ€ν°μ»€λ₯Ό λΌμ§ μκ±°λ μ λΆλΆμ΄λ μλ« λΆλΆμ λ μ μμ΅λλ€.
νμ¬ μ€ν°μ»€μ μ λΆλΆμ λ κ²½μ°μλ λ€μ μΉΈμ μ€ν°μ»€λ₯Ό λΌμ§ μκ±°λ μλ« λΆλΆλ§μ λ μ μμ΅λλ€.
νμ¬ μ€ν°μ»€μ μλ λΆλΆμ λ κ²½μ°μλ λ€μ μΉΈμ μ€ν°μ»€λ₯Ό λΌμ§ μκ±°λ μ λΆλΆλ§μ λ μ μμ΅λλ€.
μ΄ μΈκ°μ§ κ²½μ°λ₯Ό μ΄μ©νμ¬ μ νμμ ꡬν μ μμ΅λλ€.
d[0][i] += Math.max(d[1][i - 1], d[2][i - 1]);
d[1][i] += Math.max(d[0][i - 1], d[2][i-1]) + sticker[1][i];
d[2][i] += Math.max(d[0][i - 1], d[1][i-1]) + sticker[2][i];
μμ μ νμλ€μ μ΄μ©νμ¬ λμ νλ‘κ·Έλλ° λ°©μμΌλ‘
nμ΄κΉμ§μ λΌμ΄λ΄λ μ΅λ μ μλ€μ ꡬνμ¬
μ΅μ’ λ§μ§λ§ nμ΄μμ λΌμ§ μκ±°λ μ λΆλΆμ΄λ μλ« λΆλΆμ λ κ° μ€
κ°μ₯ ν° μ μκ° μ λ΅μ λλ€.
π» μ½λ
package problem.dynamic;
import java.io.*;
public class Main_9465 {
static int n;
static int t;
static int[][] d;
static int sticker[][];
static StringBuilder sb;
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
sb = new StringBuilder();
input();
System.out.println(sb.toString());
bw.flush();
bw.close();
}
public static void solve() {
d = new int[3][n+1];
for (int i = 1; i <= n; i++) {
d[0][i] += Math.max(d[1][i - 1], d[2][i - 1]);
d[1][i] += Math.max(d[0][i - 1], d[2][i-1]) + sticker[1][i];
d[2][i] += Math.max(d[0][i - 1], d[1][i-1]) + sticker[2][i];
}
int result = Math.max(d[0][n],d[1][n]);
result = Math.max(result,d[2][n]);
sb.append(result+"\n");
}
public static void input () throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
for(int i=0; i<t; i++){
n = Integer.parseInt(br.readLine());
sticker = new int[3][n+1];
for(int j=1; j<=2; j++){
String[] in = br.readLine().split(" ");
for(int k=1; k<in.length+1; k++){
sticker[j][k] = Integer.parseInt(in[k-1]);
}
}
solve();
}
br.close();
}
}