글 읽기 - 틀렸는데 왜 틀렸는지 모르겠습니다

rlarlghks970113 4년 전 0

바로 틀렸습니다라고 뜨는데 왜 뜨는지 모르겠어요 ㅜㅜ

질문 게시판에 있는 모든 반례랑 예제는 맞는데 말이죠

고수님들 도와주십쇼!!

#include <iostream>
#include <vector>

using namespace std;

vector<bool> ret(16, false);

int calc(const vector<pair<int, int>>& arr, int n, int sum, int N)
{
	//기저사례
	//시간초과일때
	if (n < 0) return sum;
	if (n + arr[n].first > arr.size()) return calc(arr, n - 1, sum, N);
	if (n + arr[n].first > N + 1)
	{
		//겹치는 구간 모든 합
		int tmpSum = 0;
		for (int i = N + 1; i < n + arr[n].first; ++i)
		{
			if (ret[i] == true)
			{
				tmpSum += arr[i].second;
			}
		}
		if (tmpSum < arr[n].second)
		{
			for (int i = N + 1; i < n + arr[n].first; ++i)
			{
				ret[i] = false;
			}
			ret[n] = true;
			

			return calc(arr, n - 1, sum - tmpSum + arr[n].second, n - 1);
		}
		return calc(arr, n - 1, sum, N);
	}
	ret[n] = true;
	return calc(arr, n - 1, sum + arr[n].second, n - 1);
}

int calc(const vector<pair<int, int>>& arr)
{
	return calc(arr, arr.size() - 1, 0, arr.size() - 1);
}

int main()
{
	int n, t, p;
	cin >> n;


	//걸리는 시간과 수익
	vector<pair<int, int>> arr(n);

	for (int i = 0; i < n; ++i)
	{
		cin >> t >> p;
		arr[i] = pair<int, int>(t, p);
	}
	
	cout << calc(arr) << '\n';

	return 0;
}

rlarlghks970113 4년 전 1

반례는 찾았네요

3 50

1 1

3 3

2 2

1 1

의 경우 52가 나와야 최대이익인데 전 50이라고 나오네요 후우....

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

문제

문제

출처

ICPC

틀렸는데 왜 틀렸는지 모르겠습니다

rlarlghks970113 4년 전 0

rlarlghks970113 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말