Baekjoon11052-카드 구매하기

백준 사이트 11052 - 카드 구매하기 문제입니다.

---

1. 문제

https://www.acmicpc.net/problem/11052

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다.
백준에서는 sliver1의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 입력 값들이 크지 않아서 for문 2개로 해결이 가능합니다.
• 처음에는 배수들만 생각해줬는데, 그것에도 문제가 있습니다. 모든 경우를 따졌습니다.

---

5. code

#include<iostream>
#include<algorithm>
using namespace std;

int n;
int dp[10001];

void Input()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> dp[i];

}
void Solve()
{
	for (int i = 2; i <= n; ++i)
	{
		dp[i] = max(dp[i - 1] + dp[1], dp[i]);
        // i까지 합들을 계산해서 갱신 위의 점화식이 맞는지는 모르지만, 맞았기에
		for (int j = 1; j <= i; ++j)
		{
			dp[i] = max(dp[i - j] + dp[j], dp[i]);
		}

		/* 처음에 실수한 배수로 계산하기
        int temp=1;
		for (int j = i; j <= n; j =i* temp)
		{
			dp[j] = max(dp[j], dp[i] * temp);
			++temp;
		}
		*/
	}
}
void printdp()
{
	for (int i = 0; i <= n; ++i)
		cout << dp[i] << " ";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	Solve();
	cout << dp[n];

}

---

6. 후기

고치는데 오래걸리진 않아서 다행이다.