<Algorithm> 193. 카드 구매하기(BJO)

1. 11052번 카드 구매하기(BJO)

   사용 알고리즘 :  DP

• DP는 정말 알다가도 모르는 류에 속하는 것 같다.  DP는 확실히 꾸준히 접해야 늘 것 같다는 생각이 많이 들었다.

• 이문제는 답을 보면서도 이해가 안되는 부분이 있어서 직접 케이스를 대입하면서 이해했다. (아래의 주석부분....)

문제에 대한 접근&생각

1. 카드의 개수가 정해져 있고 최댓값을 출력 -> DP! 

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import java.util.Scanner;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int[] card = new int[n+1];         int[] dp = new int[n+1];         /**********************************************************************          * DP를 이용해 최대치를 구한다.          *           * ex) 사야할 개수가 N = 4          *     dp[i]는 i개에 대한 최대값을 뜻함          *     dp[1]는 1개짜리 즉 첫번째 값만 가능          *     dp[2]는 1개짜리*2 or 2개짜리*1 중 최댓값           *     dp[3]는 1개짜리*3 or 1개짜리*1 + 2개짜리*1 or 3개짜리*1 중 최댓값          *               *     반복문에서 j 위의 or에 대한 처리를 담당한다.          *                *     dp[3] => dp[2] + arr[1] 2+1 = 3개(1*2가 될지 2*1이 되는지는 이전에 처리됨)          *                dp[1] + arr[2] 1+2 = 3개          *                dp[0] + arr[3] 0+3 = 3개          *               *     i의 인덱스는 개수를 의미하는 것이므로 이를 이용해 처리한다.          **********************************************************************/         for(int i = 0; i < n; i++) {             card[i+1] = sc.nextInt();         }         dp[0] = 0;         for(int i = 1; i <= n; i++) {             for(int j = 1; j <=i; j++) {                 dp[i] = Math.max(dp[i], dp[i-j]+card[j]);             }         }         System.out.println(dp[n]);     } }   Colored by Color Scripter

cs