글 읽기 - 1912번 어떤 예외가 있을까요ㅠㅠ

friendof865 6년 전 0

질문하기에 있는 테스트 케이스들은 잘 되는데 엄청 초반부터 틀렸습니다가 뜹니다ㅠ

입력받을 때 인접한 같은 부호의 수끼리 합하고, DP로 해당 위치의 수와 그 수와 연결된 수들의 합의 최댓값을 구하는 방식으로 알고리즘을 짰습니다.

(도중에 음수 혹은 0으로만 이루어질 수도 있다는 말을 듣고 main함수가 좀 많이 더럽긴 합니다..ㅈㅅ)

코드의 문제점이나 반례를 찾아주시면 감사하겠습니다~!!

또 이렇게 같은 부호끼리 더하는 것과 그냥 입력값 그대로 놔두는 것 중에 어느 것이 마지막에 결과적으로 더 빠를지 궁금합니다ㅎㅎ

#include <stdio.h>
#include <iostream>

using namespace std;

int len=0,n,arr[100001];
long long c[100001],dp[100001];

void DP(){
	int i,j;
	if(c[0]>0){
		dp[0]=c[0];
		for(i=2;i<len;i+=2){
			dp[i]=c[i];
			if(dp[i-2]+c[i-1]>0)
			dp[i]+=dp[i-2]+c[i-1];//dp[i-2], 즉 c[i-2]와 그것과 연결된 값들의 합의 최대 + c[i-1]>0이면 더한다
		}
	}
	else{//음수로 수열이 시작할 경우
		dp[1]=c[1];
		for(i=3;i<len;i+=2){
			dp[i]=c[i];
			if(dp[i-2]+c[i-1]>0)
			dp[i]+=dp[i-2]+c[i-1];
		}
	}
	
	return;
}

int main(){
	
	int i,tmp=0;
	long long max=-100000000;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf(" %d",&arr[i]);
		if(arr[i]*arr[i-1]>=0){
			tmp+=arr[i];//같은 부호의 수는 더해놓음
			if(i==n)	c[len++]=tmp;//마지막 입력에서는 저장
		}	
		else{
			c[len++]=tmp;//부호가 바뀌면 저장
			tmp=arr[i];//tmp 다시 더하기 시작
			if(i==n)	c[len++]=tmp;
		}
	}
	if(c[0]<=0&&c[1]==0){//입력값이 음수 또는 0으로만 이루어졌을 때
		for(i=1;i<=n;i++){
			if(max<arr[i])
			max=arr[i];//입력 값 중에서 가장 큰 수
		}
		cout<<max;
		return 0;
	}
	DP();
	for(i=0;i<len;i++){
		if(max<dp[i])
		max=dp[i];//dp중에서 가장 큰 수
	}
	cout<<max;
	return 0;
}

friendof865 6년 전 0

반례:

-1 0 1

찾았습니다

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

문제

문제

출처

ICPC

1912번 어떤 예외가 있을까요ㅠㅠ

friendof865 6년 전 0

friendof865 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말