[210508][백준/BOJ] 11052번 카드 구매하기
문제
입출력
풀이
민규가 N개의 카드를 사려고 한다.
1부터 N까지 카드가 존재하고 p는 각 카드의 값이다. 이를 통해 카드를 구매하는데 필요한 최대값을 구하는 문제이다.
4개의 카드가 있을때 이를 구매하는 최대값은
카드4
카드3+카드1
카드2+카드2
카드1+카드3
총 4가지 경우 중에 존재한다.
이를 코드로 구현하면 다음과 같다.
D[4] = D[4]
D[4] = D[3] + A[1]
D[4] = D[2] + A[2]
D[4] = D[1] + A[3]
점화식은 다음과 같다.
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= i; ++j)
d[i] = max(d[i], d[i - j] + A[j]);
코드
#include <bits/stdc++.h>
using namespace std;
int d[100002];
int A[100002];
int dp(int n)
{
d[1] = A[1];
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= i; ++j)
d[i] = max(d[i], d[i - j] + A[j]);
return d[n];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> A[i];
cout << dp(n);
}
Author And Source
이 문제에 관하여([210508][백준/BOJ] 11052번 카드 구매하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kwkim95/210508백준BOJ-11052번-카드-구매하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)