본문 바로가기
Algorithm/📖Baekjoon

#11052 카드 구매하기

by yewoneeee 2022. 6. 26.

# 문제

# 입력 및 출력

# 풀이

dp[n] = max(dp[0]+dp[n], dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n-1]+dp[1])

중복되는 값은 있지만 간단한 반복문으로 구현하기 위해 그냥 위의 식으로 풀었음

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> dp[i];
	}
	for (int i = 1; i <= n; i++) {
		int maxv = dp[i];
		for (int j = 1; j < i; j++) {
			maxv = max(maxv, dp[j] + dp[i - j]);
		}
		dp[i] = maxv;
	}
	cout << dp[n];
}

'Algorithm > 📖Baekjoon' 카테고리의 다른 글

#2193 이친수  (0) 2022.06.29
#1966 프린터 큐  (0) 2022.06.28
#11403 경로 찾기  (0) 2022.06.25
#1004 어린 왕자  (0) 2022.06.24
#1051 숫자 정사각형  (0) 2022.06.23

댓글