[백준 알고리즘] (DP) 9465번 Java 풀이

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

 

 

change Nxxxx -> Main && remove package lines!!!

이클립스에서 작성하면서 문제 이름으로 클래스를 생성하여 풀었기 때문에

클래스 이름을 Main으로 바꾸고, package 부분도 지우고 제출해야 정상적으로 돌아갑니다.

 

 

<풀이> - Bottom up

package dp;
 
import java.util.Scanner;
 
public class N9465 {
 
    static long data[][];
    static long d[][];
    
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int testn = sc.nextInt();
        int n;
        
        for(int i=0; i<testn; i++) {
            n= sc.nextInt();
            long data1[] = new long[n];
            long data2[] = new long[n];
            data = new long[2][n+1];
            
            for(int j=0; j<n;j++) {
                data1[j] = sc.nextLong();
            }
            for(int j=0; j<n;j++) {
                data2[j] = sc.nextLong();
            }
            
            for(int j=0; j<n;j++) {
                data[0][j] = data1[j];
                data[1][j] = data2[j];
            }
            
            System.out.println(bottomUp(n));
            
        }
    }
    
    public static long bottomUp(int n) {
        long d[][] = new long[3][n+1];
        d[0][0] = 0;
        d[1][0] = data[0][0];
        d[2][0] = data[1][0];
        
        
        
        for(int i=1; i<=n; i++) {
            d[0][i] = Math.max(d[0][i-1], Math.max(d[1][i-1], d[2][i-1]));
            d[1][i] = Math.max(d[0][i-1], d[2][i-1])+ data[0][i];
            d[2][i] = Math.max(d[0][i-1], d[1][i-1])+ data[1][i];
        }
        
        long ans = Math.max(d[0][n], Math.max(d[1][n], d[2][n]));
        
        
        return ans;
    }
 
}
 

data[][]:
데이터를 저장하는 2차원 배열

 

최근 개강과 함께 학회 리쿠르팅 면접 참여로 인해 2일동안 쉬어버렸다.... ㅠㅠ

오늘부터 다시 꾸준히!

 

 

Github: https://github.com/jaeuk9407/AlgorithmBOJ

jaeuk9407/AlgorithmBOJ