[백준/JAVA] 11052번: 카드 구매하기

🔺 문제

11052번: 카드 구매하기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        int[] A  = new int[N + 1];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] dp = new int[N + 1];
 
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= i ; j++) {
                dp[i] = Math.max(dp[i], dp[i - j] + A[j]);
            }
        }
        
        System.out.println(dp[N]);
    }
}

✅ 해결 아이디어
✔ DP
- 카드 i개를 구매하는 경우
  └ 카드 1개 가진 카드팩 구매 & 카드 i - 1 개 구입
  └ 카드 2개 가진 카드팩 구매 & 카드 i - 2 개 구입
  └ 카드 3개 가진 카드팩 구매 & 카드 i - 3 개 구입

≫ dp[ i ] =  dp[ i - n ] + P[ n ]

 

⇨ 예제 입력 및 출력 결과

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

DP,,, 일반항 형태로 정의하면서 식을 찾아보자..

 

 

1회독	2회독	3회독	4회독	5회독
V	240424

---

(참고)

✔ 멋진 점화식 구하는 과정 설명들.. 감사합니다..🙇‍♀️🙇‍♀️

[Java]백준 11052번 :: 카드 구매하기

 

[백준/11052/Java] 카드 구매하기