Search
Duplicate

카드 구매하기

주차
11주차
문제번호
11052
언어
티어
실버
유형
DP
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

Memo

접근 방법
인덱스 0부터 N - 1 까지 로직함수의 인자를 차례대로 넣어주고, 로직함수 내에서는 매개변수로 받은 값보다 작은 값을 dp 배열에 누적해 갑니다.
로직을 직관적인 예로 설명드리면,
만약 N이 5이라고 한다면, 카드팩이 5인 경우의 값, 1인 경우와 4인 경우를 더해서 만들어진 값, 2인 경우와 3인 경우를 더해서 만들어진 값. 총 3가지 경우의 최댓값이 됩니다. 이때 4인 경우는 1과 3, 2와 2, 4 로 만들 수 있는 최대값으로 만들 수 있습니다.
따라서 dp 배열을 만든 후에 앞에서 부터 차례대로 쌓아 나가면 문제를 쉽게 해결할 수 있습니다.

Code

제출 날짜

@2/23/2021

메모리

2016 KB

시간

0 ms
#include <iostream> #include <vector> size_t N; std::vector<int> P; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::cin >> N; P.resize(N + 1); for (size_t i = 1 ; i < N + 1 ; i++) std::cin >> P[i]; } void logic(size_t ind) { size_t max_ = ind / 2; int tmp; for (size_t i = 1 ; i <= max_ ; i++) { if (P[ind] < (tmp = P[i] + P[ind - i])) P[ind] = tmp; } } void solve() { for (size_t i = 1 ; i < N + 1 ; i++) logic(i); } void print_val() { std::cout << P[N]; } int main() { input(); solve(); print_val(); return (0); }
C++
복사