Baekjoon 11052 카드 구매하기 JAVA

해당 문제는 DP를 활용하여 문제를 해결하였다.

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2011052

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

​

해당 문제는 원하는 개수만큼의 카드를 구매하고자 할 때 최댓값을 구하는 문제다

​

조건

카드 i 개가 포함된 카드팩의 가격은 Pi 원이다

첫째 줄에 카드 개수 입력

둘째 줄에 Pi가 1부터 N까지 입력

​

DP를 이용하여 해결하였다

카드 1개 -> 1개 가격

카드 2개 -> 1개 +1개 가격, 2개 가격 비교

카드 3개 -> 1개 +1개 +1개 가격, 2개 +1개 가격, 3개 가격 비교

카드 4개 -> 1개 +1개 +1개 + 1개 가격, 2개 +1개 + 1개 가격, 3개 +1개 가격, 4개 가격, 2개 + 2개 가격 비교

​

카드 3개의 경우 카드 2개에서 최댓값에 +1개 한 값과 3개 가격만 비교해 주면 되고 카드 4개의 경우 3개의 경우에서 최댓값에 +1개 한 값과 4개, 2개 + 2개 값을 비교하여 주면 된다.

사실상 카드 N 개면 N-1개 + 1개의 가격, N - 2개 + 2개의 가격 ... 1개 가격 + N-1개 가격을 비교해 주면 된다.