글 읽기 - 게시판에 반례 다 넣어봤는데 틀리는게없습니다.. 반례좀 찾아주시면 감사하겠습니다

whitecafe 3년 전 0

반례좀 찾아주십쇼 C++입니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 2147000000
using namespace std;

int main()
{
	int n,i,j,maxi = -INF,sum = -INF,cnt = 0;
	cin>>n;
	if(n==1)
	{
		cin>>i;
		cout<<0;
		return 0;
	}
	vector<int> dp(n+100),map(n+100);
	for(i = 1;i<=n;i++)
	{
		cin>>map[i];
		dp[i] = map[i];
		if(map[i]==map[i-1]&&i>=2)
		{
			cnt++;
		}
	}
	if(cnt==n-1)
	{
		cout<<0;
		return 0;
	}
	for(i = 2;i<=n;i++)
	{
		maxi = -INF;
		for(j = i-1;j>=1;j--)
		{
			if(map[i]>map[j]&&dp[j]>maxi)
			{
				maxi = dp[j];
			}
		}
		dp[i] = max(dp[i],dp[i]+maxi);
		if(sum<dp[i])sum = dp[i];
	}
	cout<<sum;
	return 0;
}

exponential_e 3년 전 2

반례 드립니다.

입력
10
102 100 2 3 4 3 5 6 7 8
    
출력
100
답
102

whitecafe 3년 전 0

반례감사합니다. ㅠㅠ 근데 반례 고려해서 다시 짰는데도 예제 다 맞는데 틀렸다고나오네요.ㅠㅠ 어디가 문제일까요 ㅠ

whitecafe 3년 전 0

수정한 소스코드입니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 2147000000
using namespace std;

int map[1001],dp[1001];
int main()
{
	int n,i,j,maxi,*MAX;
	cin>>n;
	if(n==1)
	{
		cin>>i;
		cout<<i;
		return 0;
	}
	for(i = 1;i<=n;i++)
	{
		cin>>map[i];
		dp[i] = map[i];
	}
	for(i = 2;i<=n;i++)
	{
		maxi = -INF;
		for(j = i-1;j>=1;j--)
		{
			if(map[i]>map[j]&&maxi<dp[j])
			{
				maxi = dp[j];
			}
		}
		dp[i] += maxi;
	}
	MAX = max_element(dp+1,dp+n+1);
	cout<<*MAX;
	return 0;
}

ehdrmsl2001 3년 전 2

5 1 2 3 10

답 : 16

exponential_e 3년 전 1

가끔은 직접 반례를 만들어보시는 것도 연습에 많은 도움이 됩니다.

아래 예제는 [1 2 3 4 7]이 선택되어야 하는데, 10을 출력합니다.

로직이 작동하는 중에 maxi 값이 전혀 갱신되지 않는 경우가 존재하고 이에 따라 dp 배열에 음수가 저장되어 이러한 결과가 발생하고 있는 것으로 보입니다.

입력
9
10 2 9 1 2 3 4 7 6

출력
10
답
17

whitecafe 3년 전 0

답변들 정말 감사합니다. 댓글 참조해서 처음부터 설계가 맞는지 확인하면서 가야겠습니다.

whitecafe 3년 전 1

바로 해결했습니다..! 생각보다빨리됐네요

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

문제

문제

출처

ICPC

게시판에 반례 다 넣어봤는데 틀리는게없습니다.. 반례좀 찾아주시면 감사하겠습니다

whitecafe 3년 전 0

exponential_e 3년 전 2

whitecafe 3년 전 0

whitecafe 3년 전 0

ehdrmsl2001 3년 전 2

exponential_e 3년 전 1

whitecafe 3년 전 0

whitecafe 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말