백준 11052 카드 구매하기

풀이
이중 for문을 돌며 N개의 카드를 구입 시 Pn개를 구입하는 경우와 그 전의 경우의 수들 중 max값을 찾아내는 d[i] = Math.max(d[i], d[i-j]+card[j])의 점화식을 통해서 구현

주의사항
Top-down방식으로 재귀를 활용할 시 이중for문은 안의 for문을 재귀함수의 내부에 넣어서 구현한다.

소스코드
1. Top-down 방식
public class Baekjoon11052_PurchaseCard {
static int card[];
static int d[];
static public void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
card = new int[10001];
d = new int[N+1];

    st = new StringTokenizer(br.readLine());
    int index = 1;
    while(st.hasMoreTokens()){
        card[index++] = Integer.parseInt(st.nextToken());
    }
    System.out.println(maxValue(N));
	}

    static int maxValue(int n) {
        if(d[n] > 0)
	        return d[n];

    	for(int i = 1; i<=n; i++){
        	d[n] = Math.max(d[n], maxValue(n-i) + card[i]);
    	}
    	return d[n];
      }
	}

2. Bottop-up 방식

   public class Baekjoon11052_PurchaseCard {
   
       static int card[];
       static int d[];
       static public void main(String args[]) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());
       int N = Integer.parseInt(st.nextToken());
       card = new int[10001];
       d = new int[N+1];
   
       st = new StringTokenizer(br.readLine());
       int index = 1;
       while(st.hasMoreTokens()){
           card[index++] = Integer.parseInt(st.nextToken());
       }
   
       for(int i = 1; i<=N; i++){
           for(int j = 1; j<=i; j++){
               d[i] = Math.max(d[i], d[i-j]+card[j]);
           }
       }
       System.out.println(d[N]);
   }