21.09.18 기록

백준 알고리즘 1932 풀이

🎆나의 오답

-처음에는 DP를 어떻게 사용해야할지 모르겠어서 그냥 최댓값을 구하는 경로로 풀이했다.
-최댓값 구하기를 구현하고 제출해보니 오답이었고, DP를 어떤식으로 사용해야할지 감을 잡을 수 있었다.
-하지만 오늘도 막상 구현해보려니 뭔가 알 것 같으면서도 막막해서 그냥 해설을 봤다..!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1932 {
    public static int N;
    public static int[][] TRIANGLE;
    public static int centerIdx;
    public static int max = Integer.MIN_VALUE;
    public static int DP[][];
    public static int sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        TRIANGLE = new int[N+1][2*N];
        DP = new int[N][N];

        StringTokenizer st;
        centerIdx = (2*N-1)/2;
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int cntToken = st.countTokens();

            if(cntToken == 1) {
                TRIANGLE[0][centerIdx] = Integer.parseInt(st.nextToken());
            } else {
                for(int j = centerIdx -cntToken+1; j <= centerIdx +cntToken-1; j+=2) {
                    TRIANGLE[i][j] = Integer.parseInt(st.nextToken());
                }
            }
        }
        sum = TRIANGLE[0][centerIdx];
        getMax(1, centerIdx-1);
        System.out.println(max);
    }

    public static void getMax(int depth, int idx) {
        if(depth == N) {
            return;
        }

        int left = TRIANGLE[depth+1][idx-1];
        int right = TRIANGLE[depth+1][idx+1];

        if(left > right) {
            sum += left;
            getMax(depth+1, idx-1);
        } else {
            sum += right;
            getMax(depth+1, idx+1);
        }
    }
}

🎆해설

-dp의 사용을 알 듯하면서도 모르겠어서 답답했던 부분이 해설에서 그림으로 친절히 설명해주셔서 빠르고 쉽게 이해할 수 있었다.
-백트래킹 단계부터 문제가 너무 어렵게 느껴져서 매일 문제 푸는 게 너무 부담스럽고.. 하기가 싫은 요즘인데, 매일 틀리면서 나도 모르게 감을 잡는 것 같아서 문제 풀기를 그만둘 수가 없다.🤦🏻‍♀️

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1932 {
    public static int[][] TRIANGLE;
    public static Integer[][] dp;
    public static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        TRIANGLE = new int[N][N];
        dp = new Integer[N][N];
        StringTokenizer st;
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < i+1; j++) {
                TRIANGLE[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < N; i++) {
            dp[N-1][i] = TRIANGLE[N-1][i];
         }

        System.out.println(getMax(0,0));
    }

    public static int getMax(int depth, int idx) {
        if(depth == N-1) {
            return dp[depth][idx];
        }

        if(dp[depth][idx] == null) {
            dp[depth][idx] = Math.max(getMax(depth+1, idx), getMax(depth+1, idx+1)) + TRIANGLE[depth][idx];
        }
        return dp[depth][idx];
    }
}