BaekJoon 2752 보드게임

Link https://www.acmicpc.net/problem/2572

소스 결과 3148 KB / 0 ms

출처 Baekjoon , KOI 2007 고등부 3번

언어 C++ 17

분류 다이나믹 프로그래밍

 

설명

R G B 3가지 색깔이 있는 보드게임 카드를 가지고 문제의 룰을 통해 얻을 수 있는 최대 점수를 구하는 문제

 

처음에 접근을 카드를 기준으로 접근을 한게 아닌, 정점을 기준으로 접근을 했더니 아니나 다를까 메모리가 터졌다.

문제의 접근을 현재 위치와 이번에 내는 카드를 기준으로 접근을 해야했다.

현재 카드를 기준으로 접근 할 수 있는 정점의 값을 기록해 모든 카드를 소모 할 때 까지 반복한다.

 

알고리즘

1. 정점의 정보를 받아 저장한다.

2. 1번 정점을 시작으로 방문 할 수 있는 정점의 점수와 이미 저장된 정점의 점수중 높은 값을 저장해 나가며 마지막 카드까지 방문한다.

3. 출력

 

소스코드

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <string.h>

using namespace std;

const int MAX = 500;
const int CARD_MAX = 1000;

vector<pair<int, char>> adj[MAX + 1];
char card[CARD_MAX];
int costMap[CARD_MAX + 1][MAX + 1];
int n, m, k;

int max(int a, int b)
{
	return a > b ? a : b;
}

int func(int turn, int point)
{
	if (turn == n)
		return 0;

	int& res = costMap[turn][point];

	if (res != -1)
		return res;

	res = 0;

	for (auto vertex : adj[point])
	{
		int next = vertex.first;
		res = max(res, func(turn + 1, next) + (vertex.second == card[turn] ? 10 : 0));
	}

	return res;
}

int main()
{
	memset(costMap, -1, sizeof(costMap));

	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		scanf(" %c", &card[i]);

	scanf("%d %d", &m, &k);

	for (int i = 0; i < k; i++)
	{
		int x, y;
		char color;

		scanf("%d %d %c", &x, &y, &color);
		adj[x].push_back(make_pair(y, color));
		adj[y].push_back(make_pair(x, color));
	}

	printf("%d",func(0, 1));

	return 0;
}