Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 언리얼 커스텀 플러그인
- 1253번
- 데이터베이스 배움터
- SQL
- Unreal
- hackerank
- 5639
- Linux
- 백준
- FBX
- UActor
- 오손데이터읽기
- 실습
- 백준 1253번
- objtofbx
- command not found
- 언리얼 플러그인
- 1967번
- C++
- OS
- 트랜잭션 관리
- 셰그먼트트리
- 비재귀셰그먼트
- 의미와 무의미의 경계에서
- Security
- 2단계로킹
- oracle
- 1759번
- UnrealMP
- 민겸수
Archives
- Today
- Total
fatalite
카드 구매하기 - 11052번 백준 본문
문제 분류
문제 난이도 : 실버 1
문제 분류 : 다이나믹 프로그래밍
문제 리뷰
DP[j]를 j 개를 구매하는데에 걸리는 카드의 수로 정의한다.당연하게도, DP[0] = 0첫 번째 루프(i=1)에는 P_1만을 이용한다. DP[j] = P_1 * j가 된다.두 번째 루프(i=2)부터 비교를 해야한다. DP[j] = max(DP[j - 2] + P_2, DP[j]) 초록색 부분은 i = 1일 때의 값이었을 것이다....따라서 DP[j] = max(DP[j - i]+ P_i, DP[j])가 된다.
문제 소스코드
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>
using namespace std;
long Price[10001];
long long DP[1001];
void Init()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
Init();
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> Price[i];
}
DP[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; j++) {
DP[j] = max(DP[j - i] + Price[i], DP[j]);
}
}
cout << DP[n];
}
'코딩 인터뷰 > Dynamic Programming' 카테고리의 다른 글
가장 큰 증가하는 부분 수열 - 11055번 백준 (0) | 2023.10.20 |
---|---|
오르막 수 - 11057번 백준 (0) | 2023.10.14 |
파도반 수열 - 9461번 백준 (1) | 2023.10.13 |
동전 2 - 2294번 백준 (0) | 2023.10.12 |
파이프 옮기기 1 - 17070번 백준 (2) | 2023.09.24 |