[백준 11052번] 카드 구매하기 - (Java/python)

문제 링크 : https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

 

Idea

카드 n 개를 구매하기 위해서 우리는 다양한 카드 묶음을 선택해서 구매 할 수 있다.

문제 예시 처럼 카드 팩의 종류가 4가지가 있을때 4개의 카드를 구매하기 위해서 P1 을 4개 구매할 수도 있고 P4 1개를 구매할 수도 있고, 여러 조합으로 구매가 가능하다. 이때 가장 비용이 많이 드는 조합을 고르는게 정답이다.

우리는 특정 카드 개수를 구매할때 어떤 종류를 구매해야 되는지 알수가 없다.

따라서 다음과 같이 표현해볼 수 있다.

? + ? +... + ? = n 

이때 마지막 ? 에 올수 있는 경우의 수는 P1 ~ Pn 까지가 있다. 만약 마지막에 P1이 온다면 

? + ? + ... + P1 = n 이 되는 것이고 n개를 구매하기 위해 마지막으로 구매한 카드 팩이 P1이 되는 것이다.

모든 경우의 수 중에서 최대를 구하는게 목적이므로 

d[i] 를 카드 개를 구매하는 최대 비용 이라고 하면

d[i] = max(d[i-1] + P1 , d[i-2] + P2 ,    ...... , d[i-i] + Pi) 로 표현이 가능하다.

 

d[1] 은 카드 한개를 구매하는 경우 최대 비용으로 P1 한가지 경우밖에 없으므로 d[1] = P1 이 된다.

 

 

풀이

Java

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] p = new int[n+1];
        int[] d = new int[1001];
        for(int i=1; i<=n; i++)
        {
            p[i] = sc.nextInt();
        }
  
        d[1] = p[1];

        for(int i=2; i<=n; i++){
            for(int j=0; j<=i; j++){
                d[i] = Math.max(d[i-j]+p[j],d[i]);
            }
        }

        System.out.println(d[n]);


    }
}

 

Python

n = int(input())
p=[0]
p+=list(map(int,input().split()))

d=[0]*1001

d[0]=0
d[1]=p[1]

for i in range(1,n+1): # 카드팩의 개수 d[i]
    for j in range(1,i+1): # 카드팩의 구성
        d[i]=max(d[i-j]+p[j],d[i])
        
print(d[n])