1. 문제 링크
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
2. 문제 및 입출력예제
3. 문제 풀이
dp 느낌으로 풀었다.
N개의 카드를 제일 비싸게 샀을 때의 가격을 구하는 문제이다.
카드를 살 때마다의 가격을 price 배열에 저장했다.
반복문을 돌리면서 N개를 살 때의 가격을 더해가면서 더 큰 값을 sum 배열에 남겼다.
4. 코드
import java.io.BufferedReader;
import java.io.IOException;
public class Main {
private static int N, price[], sum[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
price = new int[N+1];
sum = new int[N+1];
String[] split = br.readLine().split(" ");
for(int i=1;i<N+1;i++) {
price[i] = Integer.parseInt(split[i-1]);
}
for(int i=1;i<N+1;i++) {
for(int j=1;j<=i;j++) {
sum[i] = Math.max(sum[i], sum[i-j]+price[j]);
}
}
System.out.println(sum[N]);
}
}
'ALGORITHM' 카테고리의 다른 글
백준 11650 좌표 정렬하기 (Java) (0) | 2023.03.11 |
---|---|
백준 21608 상어 초등학교 (Java) (0) | 2023.03.11 |
백준 2096 내려가기 (Java) (0) | 2023.03.09 |
백준 11057 오르막 수 (Java) (0) | 2023.03.09 |
백준 10431 줄세우기 (Java) (0) | 2023.03.08 |