-
[알고리즘-JAVA] 백준 알고리즘 9465번 - 스티커(미완)알고리즘 2019. 8. 6. 16:09
Top-Down
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; import java.lang.Math; public class Main { public static long d[][]; public static long score[][]; public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); // 테스트케이스 개수 for (int i = 0; i < t; i++) { int n = Integer.parseInt(br.readLine()); score = new long[2][n]; d = new long[n+1][3]; // 스코어 채우기 - 윗줄 StringTokenizer stk = new StringTokenizer(br.readLine()); for (int j = 0; j < n; j++) { score[0][j] = Long.parseLong(stk.nextToken()); } // 스코어 채우기 - 아랫줄 stk = new StringTokenizer(br.readLine()); for (int j = 0; j < n; j++) { score[1][j] = Long.parseLong(stk.nextToken()); } for (int j = 0; j <= 2; j++){ long temp = Calculate(n, i); } long max = 0; for (int j = 0; j <= 2; j++){ max = Math.max(max,d[n][i]); } System.out.println(max); } } public static long Calculate(int n, int k){ if (n==1){ if (k==0){ return 0; } if (k==1){ return score[0][0]; } if (k==2){ return score[1][0]; } } if (d[n][k] > 0){ return d[n][k]; } else { if (k==0){ d[n][k] = Math.max(d[n][k],Calculate(n-1, 0)); d[n][k] = Math.max(d[n][k],Calculate(n-1, 1)); d[n][k] = Math.max(d[n][k],Calculate(n-1, 2)); } if (k==1){ d[n][k] = Math.max(d[n][k],Calculate(n-1, 0) + score[0][n-1]); d[n][k] = Math.max(d[n][k],Calculate(n-1, 2) + score[0][n-1]); } if (k==2){ d[n][k] = Math.max(d[n][k],Calculate(n-1, 0) + score[1][n-1]); d[n][k] = Math.max(d[n][k],Calculate(n-1, 1) + score[1][n-1]); } } return d[n][k]; } }
'알고리즘' 카테고리의 다른 글
[알고리즘-JAVA] 백준 알고리즘 2609번 - 최대공약수와 최소공배수 (0) 2019.08.06 [알고리즘-JAVA] 백준 알고리즘 10430번 - 나머지 (0) 2019.08.06 [알고리즘-JAVA] 백준 알고리즘 11057번 - 오르막수 (0) 2019.08.05 [알고리즘-JAVA] 백준 알고리즘 10844번 - 쉬운 계단 수 (0) 2019.08.04 [알고리즘-JAVA] 백준 알고리즘 2193번 - 이친수 (1) 2019.08.03