백준 11052번 : 카드 구매하기 bfs -> 최적 dp배열

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

11052번: 카드 구매하기

예제 입력 1 복사

4 1 5 6 7

예제 출력 1 복사

10

예제 입력 2 복사

5 10 9 8 7 6

예제 출력 2 복사

50

예제 입력 3 복사

10 1 1 2 3 5 8 13 21 34 55

예제 출력 3 복사

55

예제 입력 4 복사

10 5 10 11 12 13 30 35 40 45 47

예제 출력 4 복사

50

예제 입력 5 복사

4 5 2 8 10

예제 출력 5 복사

20

예제 입력 6 복사

4 3 5 15 16

예제 출력 6 복사

18

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

int cardprice[1001]; 

struct Node {
	int cardnum;
	int maxprice;
};


void bfs(int num)
{
	queue <Node> que;
	que.push({ 0, 0 }); 
	Node node; 
	int max = 0;
	while (1)
	{
		if (que.empty())
			break;
		node = que.front();
		que.pop();
		if (node.cardnum == num)
		{
			if (max < node.maxprice)
			{
				max = node.maxprice;
			}
		}
		else 
		{
			for (int i = 1; i <= num;i++)
			{
				if (node.cardnum + i <= num)
					que.push({ node.cardnum + i, node.maxprice + cardprice[i] });
			}
		}
	}
	cout << max; 
}

int main(void)
{
	int n;
	cin >> n;
	for (int i = 1; i <= n;i++)
	{
		cin >> cardprice[i]; // index = i = 1~
	}
	bfs(n);
}

또 메모리 초과ㅜㅜ 

 

참고한 코드 

https://www.acmicpc.net/board/view/53513

글 읽기 - 어디서 틀린걸까요??

#include<stdio.h>
long long dp[1001];
long long P[1001];


int max(int a, int b)
{
	if (a > b)
		return a;
	else
		return b;
}

int price(int n)
{
	dp[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			dp[i] = max(dp[i], dp[i - j] + P[j]);
		}
	}
	return dp[n];
}
int main()
{
	int N;
	long long res;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &P[i]);
		dp[i] = 0;
	}
	res = price(N);


	printf("%lld", res);

	return 0;
}

dp[] 배열은 그 해당 숫자에 오기까지 최적의 방법을 저장해둔 배열 

만약 dp[i]자체만 했을 때가 더 크면 dp[i]를 만약 dp[i-j] + P[j]가 최적이라면 이것으로 대체시키는 방법으로 푸는 것이다. 

 

원래 

 

int price(int n)
{
	dp[0] = 0;
	if (n == 0)
		return 0;
	else if (dp[n] != 0)
		return dp[n];
	else
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= i; j++)
			{
				dp[i] = max(dp[i], dp[i - j] + P[j]);
			}
		}
	return dp[n];
}

int price() 부분이 복잡했는데 이것저것 없애도 통과됨 

 

그냥 여담이지만 이거 밑에 광고 있길래 

들어가서 열심히 40문제 풀었는데

마지막에 5달런가? 내야지 결과 나온다고 해서 결국 못 봄 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아니... 무슨.. 다 풀고나서 말해주기 어딨어.. 꼬박 40분은 푼거 같은데