링크

11052 카드 구매하기

문제

풀이

잘하는 친구에게 Top-down방식을 배우면서 풀이를 받았다

이거는 N을 넣어서 앞으로 땡기면서 값을 구하는거

반대로 0을 넣어서 N의 값을 구하는거

이 풀이를 보면서 풀었다. 아직 top-down방식이 잘 떠오르지 않고 재귀도 부족한 것 같다.
dp문제들을 top-down방식으로 풀면서 공부해야겠다.

코드

import java.awt.desktop.PreferencesEvent;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.nio.Buffer;
import java.sql.Array;
import java.util.*;

public class Main {

    public static int[] dp;
    public static int[] cards;

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

        dp = new int[n+1];
        cards = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1;i<=n;i++){
            cards[i] = Integer.parseInt(st.nextToken());
        }
        
        System.out.println(recursive(0));
//        System.out.println(Arrays.toString(dp));
    }

    public static int recursive(int dept){
        if(dept >= dp.length){
            return 0;
        }

        if(dp[dept] != 0){
            return dp[dept];
        }

        int result = 0;
        for(int i=1;i<cards.length;i++){
            if(dept + i >= dp.length) continue;

            int element = recursive(dept+i) + cards[i];
            result = Math.max(element, result);
        }

        dp[dept] = result;

        return dp[dept];
    }


}