글 읽기 - dp 풀이 질문

lacrimak 5년 전 0

색종이를 크기 순으로 내림차순 정렬 한 뒤

solve(m)을 m번째 색종이를 놓았을 때 m번째 색종이 포함 그 위로 쌓을 수 있는 색종이의 최대값으로 정의하고 함수를 작성했는데 틀렸습니다 가 나오네요

어느 부분에 잘못된 부분이 있는지 질문 드립니다.

혹은 잘못된 반례를 찾아주실 수 있을까요?

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int d[100];
vector<pair<int, int> >  a;
bool comp(pair<int, int > a, pair<int, int > b);
int solve(int m);
int main(void) {
	scanf("%d", &n);
	a.reserve(n);
	for (int i = 0; i < n; ++i) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		if (t1 < t2) swap(t1, t2);
		a.push_back(make_pair(t1, t2));
	}
	sort(a.begin(), a.end(), comp);
	memset(d, -1, sizeof(d));
	solve(0);
	int maxv = -1;
	for (int i = 0; i < n; ++i) maxv = max(maxv, d[i]);
	printf("%d", maxv);
	return 0;
}

int solve(int m) {
	if (m >= n) return 0;
	int &ret = d[m];
	if (ret != -1) return ret;
	ret = 1;
	for (int i = m+1; i < n; ++i) {
		if (a[m].first >= a[i].first && a[m].second >= a[i].second) {
			ret = max(ret, solve(i)+1);
		}
	}
	return ret;
}

bool comp(pair<int, int > a, pair<int, int > b) {
	return a.first*a.second > b.first*b.second;
}

djm03178 5년 전 0

가장 큰 색종이를 사용하지 않는 것이 최적일 수 있습니다.

lacrimak 5년 전 0

@djm03178

아예 작은 색종이를 사용하지 못하는 경우가 있었네요

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dp 풀이 질문

lacrimak 5년 전 0

djm03178 5년 전 0

lacrimak 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말