풀이 방법
DP의 Bottom-Up 방식을 이용해서 풀이했다.
맨앞의 스티커 두개를 먼저 넣어주고 다음 스티커부터 대각선방향으로 더한 값과 서로 변을 공유하는 스티커 중 더 큰값을 찾아주었다.
내 코드
package com.company;
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
for (int j = 0; j < T; j++) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int array[][] = new int[2][N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
array[0][i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
array[1][i] = Integer.parseInt(st.nextToken());
}
int dp[][] = new int[2][N + 1];
dp[0][1] = array[0][1];
dp[1][1] = array[1][1];
for (int i = 1; i <= N; i++) {
dp[0][i] = Math.max(dp[1][i - 1] + array[0][i], dp[0][i - 1]);
dp[1][i] = Math.max(dp[0][i - 1] + array[1][i], dp[1][i - 1]);
}
System.out.println(Math.max(dp[0][N], dp[1][N]));
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
평범한 배낭 - 12865번 (0) | 2021.10.05 |
---|---|
징검다리 건너기 - 21317번 (0) | 2021.10.05 |
좋은 수열 - 2661번 (0) | 2021.10.04 |
말이 되고픈 원숭이 - 1600번 (0) | 2021.10.04 |
뒤집기 II - 1455번 (0) | 2021.10.04 |