글 읽기 - 반례 하나만 찾아주시면 정말 감사하겠습니다ㅠㅜ

dkjjkcoding 3년 전 0

저는 개인적으로 완벽하다고 생각했는데 틀렸다고 나오더라구요,,ㅎ

#include<iostream>
#include<algorithm>

#define MAX 100000
using namespace std;

int n,ans;
int inp[MAX];
int dp[MAX][2]; // removed n/y

int main(){
	cin>>n;
	for(int i=0;i<n;i++){ cin>>inp[i]; }
	
	dp[0][0]=inp[0];
	dp[0][1]=0;
	ans=max(dp[0][0],dp[0][1]);
	for(int i=1;i<n;i++){
		dp[i][0]=max(dp[i-1][0]+inp[i],inp[i]);
		dp[i][1]=max(dp[i-1][0],dp[i-1][1]+inp[i]);
		if(ans<dp[i][0]||ans<dp[i][1]){ ans=max(dp[i][0],dp[i][1]); }
	}
	
	cout<<ans;
	
	return 0;
}

shg9411 3년 전 1

반례입니다.

1
-3

dkjjkcoding 3년 전 0

감사합니다ㅠㅜ

그리고 저 완전 이상하게 했더라구욯ㅎㅎㅎ

2차원 배열 인덱스를 완전 헷갈렸던거 같아요

우선 이렇게 고쳐봤는데 알려주신 반례도 반영해서 다시 고쳐볼께요!! 감사합니다!!

#include<iostream>
#include<algorithm>

#define MAX 100000
using namespace std;

int n,ans;
int inp[MAX];
int dp[2][MAX]; // removed n/y

int main(){
	cin>>n;
	for(int i=0;i<n;i++){ cin>>inp[i]; }
	
	dp[0][0]=inp[0];
	dp[1][0]=0;
	ans=max(dp[0][0],dp[0][1]);
	for(int i=1;i<n;i++){
		dp[0][i]=max(dp[0][i-1]+inp[i],inp[i]);
		dp[1][i]=max(dp[0][i-1],dp[1][i-1]+inp[i]);
		if(ans<dp[0][i]||ans<dp[1][i]){ ans=max(dp[0][i],dp[1][i]); }
	}
	
//	for(int i=0;i<2;i++){
//		for(int j=0;j<n;j++)
//			cout<<dp[i][j]<<' ';
//		cout<<'\n';
//	}
	cout<<ans;
	
	return 0;
}

shg9411 3년 전 0

배열 인덱스의 경우 원래처럼 하셔도 문제는 없습니다, 가로 세로축이 어떻게 되었던간에 그에 맞게 사용하시면 상관이 없으니까요.

skysign 3년 전 0

제가 문제 풀이한 방식과는 다른 방식으로 풀이하신 것 같네요. ^^a

나중에 한번 코드 리뷰해 봐야겠습니다.

제가 푼 풀이 공유해드립니다.

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

문제

문제

출처

ICPC

반례 하나만 찾아주시면 정말 감사하겠습니다ㅠㅜ

dkjjkcoding 3년 전 0

shg9411 3년 전 1

dkjjkcoding 3년 전 0

shg9411 3년 전 0

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말