백준 5535번 패셔니스타 C/C++ 풀이

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

 

DP 문제

 

전의 선택한 옷의 화려함 정도와 현재의 날짜를 요소로 두고 동적계획법을 사용하였다.

 

어렵지 않기 때문에 나머지는 코드로 설명

 

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAX 201

FILE* in = fopen("input.txt", "r");

int n, d;
int tmp[MAX];
int min_tmp[MAX];
int max_tmp[MAX];
int cool[MAX];
int cache[101][MAX];

//재귀를 사용한 DP
int dp(int coolness, int day) {
	//d 날짜가 됐다면 return
	if (day == d)
		return 0;
    //메모이제이션 활용
	if (cache[coolness][day] != -1)
		return cache[coolness][day];
	int ret = 0;
    //전체 옷들을 순회한 후 가장 큰 값을 return 값으로 사용
	for (int i = 0; i < n; i++)
	{
		if (tmp[day] < min_tmp[i] || tmp[day] > max_tmp[i])
			continue;
		int tmp = dp(cool[i], day + 1) + abs(coolness - cool[i]);
		ret = max(ret, tmp);
	}
	return cache[coolness][day] = ret;
}

int main() {
	fscanf(in, "%d %d", &d, &n);
	for (int i = 0; i < d; i++)
	{
		fscanf(in, "%d", &tmp[i]);
	}
	for (int i = 0; i < n; i++)
	{
		fscanf(in, "%d ", &min_tmp[i]);
		fscanf(in, "%d ", &max_tmp[i]);
		fscanf(in, "%d ", &cool[i]);
	}
	memset(cache, -1, sizeof(cache));
	int ans = 0;
    //초기값 세팅
	for (int i = 0; i < n; i++)
	{
		if (tmp[0] < min_tmp[i] || tmp[0] > max_tmp[i])
			continue;
		int tmp = dp(cool[i], 1);
		ans = max(ans, tmp);
	}
	printf("%d", ans);
}