문제:
https://www.acmicpc.net/problem/11052
접근 :
- 카드를 최댓값으로 N개 구매하기 위해서는 1 부터 N까지 구매 최대값을 알고 있어야한다.
- 카드 1개를 살때 최대값 (dp[1])은, card[1]이 최대값이다.
- 카드 2개를 살때 최대값 (dp[2])은 , card[1]을 2번 구매하는 값과 card[2] 중 더 큰 값이다.
- dp[3] 은, dp[1] + dp[2] 과 card[3] 중 더 큰 값이다.
- dp[4] = dp[1] + dp[3] , dp[2] + dp[2], num[4] 중 가장 큰 값이다.
- dp[5] = max { (dp[1] + dp[4]), (dp[2] + dp[3]), (card[5]) }
- dp[n] = max{ (dp[1] + dp[n-1]) , (dp[2] + dp[n-2]), º º º, (dp[n/2] + dp[n - n/2] ) , (card[n]) }
코드 구현 :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
int[] nums = new int[n+1];
String[] inputs = br.readLine().split(" ");
for(int i = 1 ; i <= n ; i++) nums[i] = Integer.parseInt(inputs[i-1]);
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i/2; j++) {
dp[i] = Math.max(dp[i], dp[j] + dp[i - j]);
}
dp[i] = Math.max(dp[i], nums[i]);
}
System.out.println(dp[n]);
}
}
'JAVA > Coding Test' 카테고리의 다른 글
[JAVA] 백준 2156 포도주_DP (0) | 2024.06.24 |
---|---|
[JAVA] 백준 2011 암호코드 _DP (0) | 2024.06.21 |
[JAVA] 백준 3055 탈출_BFS (0) | 2024.06.18 |
[JAVA] 백준 14713 앵무새_포인터 (0) | 2024.06.18 |
[JAVA] 백준 3190 뱀_구현 (0) | 2024.06.17 |