11052 카드 구매하기

 

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

11052번: 카드 구매하기

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
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());
		StringTokenizer st = new StringTokenizer(br.readLine(), " " );
		int card [] = new int [N+1] ;
		
		for(int i=1; i<=N;i++) {
			card[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(card[j]+dp[i-j],dp[i]);
			}
		}
		System.out.println(dp[N]);
	}
}

 

dp 를 잘 몰라서 참고해서 풀었다.

예시 입력2번에 나온 자료를 바탕으로 보면

 

5

10 9 8 7 6

 

초기 상태는,

card[i] : card i개 포함된 카드팩의 가격

card[1] =10 , card[2]= 9, card[3] =8 card[4]=7 card[5]=6

 

dp[i] = card i개를 구매하기 위해 지불해야 하는 최대 금액

dp[1]=0, dp[2]=0, dp[3]=0, dp[4]=0, dp[5]=0

이다.

일단 초기에 값은 0이고, 동적계획법에 의해 값이 바뀐다.

아래 설명에서 알 수 있다.

 

동적 계획법의 식을 생각해보면,

dp[i]= card[j]+dp[i-j]인데,

이는, 

dp[i] ( card i개를 구매하기 위해 지불해야 하는 최대 금액)

= card[j](card j개 포함된 카드팩의 가격)

+ dp[i-j] ( card i-j개를 구매하기 위해 지불해야 하는 최대 금액)

 

이 된다.

 

 

dp[i] = Math.max(card[j]+dp[i-j],dp[i]);

이렇게 표현한 것은,

초기에 dp[1]=0 인데,

card[j]+dp[1-j]랑 비교하여 더 큰 값을 dp[1]로 입력시키는 것이다.

 

더 자세히 설명해서

i=1, j=1이라면

dp[1]= Math.max(card[1]+dp[0],dp[1]);

이렇게 되고, 

card[1]+dp[0]= 10, dp[1]=0 이기에

dp[1]= 10 이 된다.

 

그리고 dp[2] = Math.max(card[j]+dp[2-j],dp[2]); 인데,

j=1 이라면

dp[2]= Math.max(card[2]+dp[1],dp[2])  =Math.max(9+10, 0)=19

이렇게 된다.

 

그리고 마지막 for문에서 j<=i 인 것은

dp[i] = Math.max(card[j]+dp[i-j],dp[i]);

여기서, dp[i-j]에서 i-j가 양수여야 하고

i-j >= 0 

i >= j가 된다.

 

 

참고 자료 : 

 

https://velog.io/@gloriousmin77/%EB%B0%B1%EC%A4%80-11052-%EC%B9%B4%EB%93%9C-%EA%B5%AC%EB%A7%A4%ED%95%98%EA%B8%B0-java

백준 11052 카드 구매하기 java