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

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

11052번: 카드 구매하기

코드설명

DP문제입니다.

 

처음에는 아래의 예시가 있다고 했을떄,

4
3 5 15 16

4개의 카드를 사용할때

1개의 카드 구매할떄와 3개의 카드 구매할떄가 18 로 최대값입니다.

처음에는 DP값을 이전 카드값과 합치는 연산을 진행하지 않아서 틀렸었습니다.

1개의 카드와 3개의 카드를 합칠떄도 고려합니다.

 

핵심로직

int[] dp = new int[N+1];
for(int i=1;i<=N;i++) {
    int idx = i;
    int cost = arr[i];

    for(int j=i; j<=N;j++) {
        dp[j] = Math.max(dp[j], dp[j - i] + cost);
    }

}

 

 

코드

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

 

 

처음에 모든 경우를 고려하지 않은 코드

4
3 5 15 16

위의 예시에서 예로들면, p3 + p1 = 18 인데, 해당사항을 고려하지않음.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int N;
	public static int[] arr;
	public static int[] dp;
	public static int answer;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	int[] dp = new int[N+1];
    	for(int i=1;i<=N;i++) {
    		int idx = i;
    		int cost = arr[i];
    		
    		int nCost = cost;
    		for(int j=i; j<=N;j+=i) {
    			dp[j] = Math.max(dp[j], nCost);
        		nCost += cost;
    		}
			
    	}
        
    	System.out.println(dp[N]);
    }
    
    
}