글 읽기 - 테스트 케이스 추가 요청

thereisnowindbag 3년 전 0

입력 :

출력

이 코드는 2를 출력하나 맞다고 나옵니다.

#include <iostream>

#define MAXN 2005

using namespace std;

typedef long long ll;

int N;
ll cake[MAXN];
ll DP[MAXN][MAXN];

int aClock(int pos)
{
	return (pos + 1) % N;
}

int clock(int pos)
{
	return (N + pos - 1) % N;
}

ll max(ll a, ll b)
{
	return (a > b ? a : b);
}

ll min(ll a, ll b)
{
	return (a < b ? a : b);
}

ll select(int start, int end)
{
	if (DP[start][end] != 0)
		return DP[start][end];

	// ** 문제 코드 ** 이렇게 될 시 조각을 나누지 않은 (N == 1인) 테스트 케이스의 경우
	// main함수 부분의 ... + cake[i] ... 부분과 이 부분이 중복돼 2 * cake[i] 가 되어 틀려야 하나 맞다고 나옴
	if (start == end)
	{
		return cake[start];
	}
	if (clock(start) == end)
	{
		return 0;
	}

	ll ret;
	
	ll tmp1 = (cake[aClock(start)] > cake[end] ? select(aClock(aClock(start)), end) : select(aClock(start), clock(end)) ) + cake[start];
	ll tmp2 = (cake[start] > cake[clock(end)] ? select(aClock(start), clock(end)) : select(start, clock(clock(end))) ) + cake[end];
	
	ret = max(tmp1, tmp2);

	return DP[start][end] = ret;
}


// 기본 아이디어 : 재귀 + DP를 통한 최대값 검색
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> cake[i];
	}

	// 첫 케이크를 뜨는 조건은 따로 for문을 통해 구현 해주어야한다.
	ll maxVal = -1;
	for (int i = 0; i < N; ++i)
	{
		bool aClock_chosen = (cake[aClock(i)] > cake[clock(i)] ? true : false);

		if (aClock_chosen)
			maxVal = max(maxVal, select(aClock(aClock(i)), clock(i)) + cake[i]);
		else
			maxVal = max(maxVal, select(aClock(i), clock(clock(i))) + cake[i]);
	}

	cout << maxVal;

	return 0;
}

startlink 2년 전 0

재채점했습니다.

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

문제

문제

출처

ICPC

테스트 케이스 추가 요청

thereisnowindbag 3년 전 0

startlink 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말