글 읽기 - 어디가 틀렸는지 모르겠습니다.......

hnryu 7년 전 0

어떠한 예외가 있는지 모르겠습니다.... ㅜㅜ 조언부탁드립니다.

#include<stdio.h>

#define max(x,y) x>=y?x:y
int A[1001];
long long dp[1001];
int main(void) {

	int n;
	scanf("%d", &n);

	int i, j;
	for (i = 1; i <= n; i++)	scanf("%d", &A[i]);

	long long maxlen = dp[1];
	for (i = 1; i <= n; i++) {
		dp[i] = 1;
		for (j = 1; j < i; j++) {
			if (A[i] < A[j] && dp[j] <= dp[i]) 
				dp[i] = dp[j] + 1 ;
		}
		maxlen = max(maxlen, dp[i]);
	}
	printf("%lld", maxlen);
}

sksdong1 7년 전 0

아래 조건에 잘못된 부분이 있어여

if (A[i] < A[j] && dp[j] <= dp[i]) 
	dp[i] = dp[j] + 1 ;

sksdong1 7년 전 1

그냥 틀린 부분만 수정하면 dp[j] >= dp[i]로 바꿔 주면 됩니다.

이유를 설명하면

최장 감소 수열을 구하기 위해서 A[i] < A[j] 인 경우 ( j < i ), i번 인덱스는 j번 인덱스의 수보다 작기 때문에 j번 인덱스의 감소 수열의 길이 +1이 될 수 있음을 알 수 있죠. 이 때 둘 중 더 긴 것을 구해야 겠죠. 따라서 dp[i] = max(dp[i], dp[j]+1)가 이것의 의미가 되고, dp[j] < dp[i] 인 경우는 무조건 dp[i]를 택해야 합니다. 따라서 위의 조건이 틀렸습니당.

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠습니다.......

hnryu 7년 전 0

sksdong1 7년 전 0

hnryu 7년 전 0

sksdong1 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말