글 읽기 - 예외 케이스를 못찾겠습니다

tddhot2 6년 전 0

안녕하세요.

제대로 dp가 작동하는 지 알아보기 위해 각 인덱스 마다 출력해서 확인해봐도 틀린 부분이 없는데

틀렸다고 나오네요....

혹시 시간이 여유있으시고, 허접 코더를 도와주실 큰 자비를 베풀어주신다면 잠깐만 봐주시고

틀린 부분 지적 부탁드리겠습니다. 좋은 주말 되세요!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> vec;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vec.push_back(a);
	}
	vector<int> ans(n, 0);
	vector<int> result(n, 0);
	ans[0] = 1;
	result[0] = vec[0];
	int sum;
	for (int i = 1; i < n; i++)
	{
		int max(0);
		sum = result[0];
		for (int j = 0; j < i; j++)
		{
			if (vec[i] > vec[j] && ans[j] > max)
				max = ans[j];
		}
		sum = vec[i]+max;
		ans[i] = sum;
		result[i] = sum;
	}

	for (vector<int>::iterator p = ans.begin();
		p != ans.end(); ++p)
		cout << *p << " ";
	cout << "\n" << endl;
	sort(result.begin(), result.end());


	cout << result[n - 1] << endl;
	return 0;
}

kookmin20103324 6년 전 1

3 10 2 7 11 5 13 8

답은 3+10+11+13 = 37이 되어야 하는데

위의 소스에서는 35가 나오네요

kookmin20103324 6년 전 1

20번째 라인에서 ans[0] = 1로 해서 그렇습니다.

처음에 무조건 숫자 1이 나오는게 아닙니다.

tddhot2 6년 전 0

시간 내셔서 답변해주셔서 감사드립니다!

참고해서 해보도록 하겠습니다.

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

문제

문제

출처

ICPC

예외 케이스를 못찾겠습니다

tddhot2 6년 전 0

kookmin20103324 6년 전 1

kookmin20103324 6년 전 1

tddhot2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말