글 읽기 - 나와있는 예외를 입력했을 때 모두 맞는데 틀렸다고 나옵니다 ㅠㅠ

j_young97 4년 전 0

질문글에 있는 예외들과 제가 찾은 예외들을 모두 입력했을 때 맞게 답이 나오는데 제출하면 틀렸다고 나옵니다ㅠㅠ

혹시 제가 못찾은 예외가 있거나 코드상 오류가 있나요?

#include <stdio.h>
#define MAX(x,y) ((x)>(y)?(x):(y))

int main(){
	// dp=부분 수열의 합  
	int input, a[1000], i, j, dp[1000]={}, big_max=0;
	
	scanf("%d", &input);
	
	for(i=0;i<input;i++)
		scanf("%d", &a[i]);
	
	dp[0]=a[0];

	for(i=1;i<input;i++){
		big_max=0;
		for(j=0;j<i;j++){
			if(a[i]>a[j])
				big_max=MAX(dp[j]+a[i], big_max);
			else	// 만약 현재 위치 앞의 배열에 현재의 값보다 작은게 없다면 현재의 값 혼자 가장 큰 부분수열이 되므로  
				big_max=a[i];
		}
		dp[i]=big_max;		
	} 
	for(i=0;i<input;i++)
		big_max=MAX(big_max, dp[i]);
		
	printf("%d", big_max);
} 

pch6828 4년 전 0

21번 줄을 big_max = MAX(a[i], big_max);로 바꾸셔야 하네요. 앞에서 구한 big_max가 이미 존재한다면 현재 보고 있는 j번째 숫자가 i번째 숫자보다 작아도 big_max는 변화하지 않습니다.

설명을 잘못했네요ㅠㅜㅠㅜ 죄송합니다
좀 더 정확하게 설명드리자면... 앞에서 이미 i번째 수보다 작은 j번째 수를 찾아서 big_max를 업데이트했다면 그다음 j번째 수가 i번째 수보다 작지 않다고 해서 big_max를 a[i]로 초기화할 필요는 없어요. big_max는 (제가 이해한 것이 맞다면) 이미 구한 dp값 중에서 조건에 맞는 가장 큰 값에 a[i]를 더한 것이니까, 하나라도 조건에 맞는 것이 존재했다면 그 다음 것이 조건에 맞지 않아도 상관이 없죠.
big_max = MAX(a[i], big_max);로 수정해서 채점해보니 AC를 받았습니다

j_young97 4년 전 0

다른 반례를 잡기 위해 else문을 넣었던건데 그런 오류가 있었네요ㅎㅎ

시간내주셔서 감사합니다!

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

문제

문제

출처

ICPC

나와있는 예외를 입력했을 때 모두 맞는데 틀렸다고 나옵니다 ㅠㅠ

j_young97 4년 전 0

pch6828 4년 전 0

pch6828 4년 전 1

j_young97 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말