글 읽기 - dp를 재귀로 풀었는데 빠진 케이스가 있을까요

shg3411 6년 전 0

각각의 그림을 dp로 설정하고 dp[i]는 'i를 포함한 최대로 구할 수 있는 그림의 가격'으로 문제를 풀었습니다.

그리고 마지막에 dp배열을 전체 탐색 하면서 최대의 값을 찾아서 최종 값을 구했는데

애초에 설정한 dp[i]에 대한 정의가 잘못되었는지 궁금합니다.

아니면 예외케이스가 어떤것들이 있을지 한번 고민해주시겠나요

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int N, S;
long long Max = 0;
int pic[300001][2];
int visit[300001];
long long dp[300001];

int compare(const void *a, const void *b) {
	return strcmp((char*)a, (char*)b);
}

long long go(int num) {
	if (pic[N][0] - pic[num][0] < S)
		return dp[num] = pic[num][1];

	if (visit[num] != 0) return dp[num];

	visit[num] = 1;
	dp[num] = pic[num][1];
	long long m = 0;
	for (int i = num + 1; i <= N; i++) {
		if (S <= pic[i][0] - pic[num][0]) {
			long long tmp = go(i);
			if (tmp > m)
				m = tmp;
		}
	}
	return dp[num] += m;
}

int main() {
	cin >> N >> S;
	for (int i = 1; i <= N; i++)
		cin >> pic[i][0] >> pic[i][1];
	
	qsort(pic, N, 2 * sizeof(int), compare);
	
	for (int i = 1; i <= N; i++)
		go(i);

	for (int i = 1; i <= N; i++)
		if (Max < dp[i]) Max = dp[i];


	cout << Max << endl;

	return 0;
}

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

문제

문제

출처

ICPC

dp를 재귀로 풀었는데 빠진 케이스가 있을까요

shg3411 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말