[백준] 11052 - 카드 구매하기 (JAVA)

1. 소요시간 : 30분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 1
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/11052
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

dp 를 사용했다.

2. 사고과정

처음엔 그리디 알고리즘이라고 생각했다. dp 유형 카테고리를 골라서 들어갔음에도 이건 그리디 아닌가? 하고 말이다. 각각 1장씩으로 나눴을 때 카드 가격이 가장 높은 것을 더해주면 된다고 생각했으나 그렇게 했을 경우에는 딱 n개에 맞춰서 할 수 없다. n개 초과가 불가능하므로.
그렇기에 이 문제는 dp 로 해결하여야 한다.

3. 풀이과정

점화식을 세워보자면 이렇다.
n이 1개일 때의 최대는 arr[1] 자신이다.
n이 2개일 때의 최대는
(1) n이 1이었을 때의 최대 (dp[1]) 에다가 arr[1]를 더한 것
(2) 그냥 arr[2] 중에서 더 큰 값이다.

n이 3일 때의 최대는
(1) n이 1이었을 때의 최대 (dp[1]) 에다가 arr[2] 를 더한 것
(2) n이 2었을 때의 최대 (dp[2]) 에다가 arr[1] 을 더한 것
(3) 그냥 arr[3]
....
이렇게 반복하다 보면 점화식을 유도해 낼 수 있다.
dp[i] = Math.max(dp[i], dp[i-j]+arr[j])

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;


		int n=Integer.parseInt(br.readLine());
		
		int dp[]=new int[n+1];
		int arr[]=new int[n+1];
		st=new StringTokenizer(br.readLine());
		for(int i=1;i<arr.length;i++)
			arr[i]=Integer.parseInt(st.nextToken());
		for(int i=1;i<dp.length;i++) {
			for(int j=1;j<=i;j++) {
				dp[i]=Math.max(dp[i],dp[i-j]+arr[j]);
			}
		}
		System.out.println(dp[n]);

	}
}

5. 결과

6. 회고

못 풀어서 다른 사람의 풀이를 봐버렸지만
이제 다른 사람의 풀이를 봤을 때 이해는 갈 정도의 수준까지는 온 것 같다.
그래서 더 아쉽기도 하다. 어떻게 하면 점화식을 잘 유도해낼 수 있을까?

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212