글 읽기 - 반례를 알고 싶습니다.

adfsfsf 5년 전 0

변수 2개짜리 dp가 가능하다는 글을 보고 구상한 코드입니다. 가장 긴 반례를 빼고는 다 성립했습니다.

#include <iostream>
using namespace std;
long int m, now, n, p, i, ch;
int main(void)
{
	cin >> n;//입력 받을 수는 n개
	for (i = 0; i < n; i++)
	{
		cin >> p;//i+1번째 수를 입력받음
		if (i == 0)//첫 수일 경우
		{
			m = p;//최댓값은 p
			now = p;//현재 합 값도 p
            continue;//잘못 넣었습니다. 없애고서 실험해주세요.
		}
		if (ch == 1 && p + now > 0)//한 번이라도 양수가 나온 적이 있으며, 현재 수를 더했을 때 양수가 된다면
			now += p;//현재 합 값은 p를 추가한 값
		else
		{
			now = p;//이외에는 p를 현재 합 값으로
			if (ch == 0 && now > 0)
				ch = 1;//현재 합이 0 이상이라는 것은 양수가 한 번이라도 나왔다는 뜻. ch가 0이면 나온 적이 없다는 뜻
		}
		m = (m > now ? m : now) > p ? (m > now ? m : now) : p;//이전 now 값이 음수여서 p 값이 현 최댓값일 수 있음.
	}
	cout << m << endl;//최댓값 출력
	return 0;
}

portableangel 5년 전 0

1 1

작은 반례는 직접 만드는 연습을 하시는 것이 좋습니다.

adfsfsf 5년 전 0

1 1

답 : 2

제대로 나옵니다.

portableangel 5년 전 0

UB가 없는지 한 번 살펴보시는 것이 좋겠네요.

아래는 다른 컴파일러에서의 실행 결과입니다.

https://ideone.com/QpYHtk

adfsfsf 5년 전 0

UB가 무엇인가요?

portableangel 5년 전 0

undefined behavior의 줄임말로, 표준에 정의되지 않은 동작을 의미합니다.

예를 들면 동일한 우선순위를 갖는 여러 연산이 한 줄에 작성되어 있을 때, 무엇이 먼저 실행될지 결정할 수 없는 경우

컴파일러의 구현에 따라 다른 순서로 실행되기도 합니다.

adfsfsf 5년 전 0

그리고, 죄송합니다. 아래 코드로 다시 한 번 봐 주세요. 주석은 생략되었지만, 위 코드의 14번 줄 continue; 만 제거한 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;
long int m, now, n, p, i, ch;
int main(void)
{
	cin >> n;
	for (i = 0; i < n; i++)
	{
		cin >> p;
		if (i == 0)
		{
			m = p;
			now = p;
		}
		if (ch == 1 && p + now > 0)
			now += p;
		else
		{
			now = p;
			if (ch == 0 && now > 0)
				ch = 1;
		}
		m = (m > now ? m : now) > p ? (m > now ? m : now) : p;
	}
	cout << m << endl;
	return 0;
}

adfsfsf 5년 전 0

처음에 올린 코드는 실수로 continue를 추가한 코드였습니다.

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

문제

문제

출처

ICPC

반례를 알고 싶습니다.

adfsfsf 5년 전 0

portableangel 5년 전 0

adfsfsf 5년 전 0

portableangel 5년 전 0

adfsfsf 5년 전 0

portableangel 5년 전 0

adfsfsf 5년 전 0

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말