코테 공부
[DP] 스티커(백준 9465번, 자바)
DaEun_
2023. 2. 23. 10:58
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
1. 시간초과.....
문제 이해 잘못함..
스티커가 떼질 때, 위 아래로 인접해있는 스티커가 같이 떼진다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class P9465 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int T=Integer.parseInt(br.readLine());
String s;
int[][] num;
int[][] dp;
int answer=-1;
for(int t_c=1; t_c<=T;t_c++) {
int N=Integer.parseInt(br.readLine());
num=new int[2][N];
dp=new int[2][N];
answer=-1;
for(int i=0;i<2;i++) {
StringTokenizer st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
num[i][j]=Integer.parseInt(st.nextToken());
dp[i][j]=num[i][j];
}
}
for(int i=0;i<N;i++) {
for(int j=i+2;j<N;j++) {
dp[0][j]=Math.max(dp[0][j], dp[0][i]+num[0][j]);
answer=Math.max(answer, dp[0][j]);
}
for(int j=i+1;j<N;j++) {
dp[1][j]=Math.max(dp[1][j], dp[0][i]+num[1][j]);
answer=Math.max(answer, dp[1][j]);
}
for(int j=i+1;j<N;j++) {
dp[0][j]=Math.max(dp[0][j], dp[1][i]+num[0][j]);
answer=Math.max(answer, dp[0][j]);
}
for(int j=i+2;j<N;j++) {
dp[1][j]=Math.max(dp[1][j], dp[1][i]+num[1][j]);
answer=Math.max(answer, dp[1][j]);
}
}
System.out.println(answer);
}
}
}
2. 정답
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_9465_스티커 {
static int[][] score, dp;
static int answer=0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int T=Integer.parseInt(br.readLine());
for(int t_c=1;t_c<=T;t_c++) {
int N=Integer.parseInt(br.readLine());
answer=-1;
score=new int[2][N];
dp=new int[2][N];
int max1=0; int max2=0;
for(int i=0;i<2;i++) {
StringTokenizer st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
score[i][j]=Integer.parseInt(st.nextToken());
dp[i][j]=score[i][j];
}
}
if(N>=2 ) {
dp[0][1]+=dp[1][0];
dp[1][1]+=dp[0][0];
}
for(int i=2;i<N;i++) {
dp[0][i]=Math.max(dp[1][i-2], dp[1][i-1])+dp[0][i];
dp[1][i]=Math.max(dp[0][i-2], dp[0][i-1])+dp[1][i];
}
answer=Math.max(dp[0][N-1], dp[1][N-1]);
System.out.println(answer);
}
}
}