LIS (최장 증가 부분수열) 문제.. jspac http://www.algospot.com/problems/read/LIS 그냥 잘 알려진 알고리즘대로 구현했는데요.. 예제로 주어진 수열들에 대해선 다 맞는 답을 내놓는데, submit을 하면 계속 WA가 뜨네요.. 제가 구현을 잘못 한건지... 일단 소스는 아래와 같은데, 어디가 잘못된 건가요? #include const int MAX_LEN = 500; int main(void) { int t, T, n, N, seq[MAX_LEN], k, len, max_len, len_lis[MAX_LEN]; scanf("%d", &T); for (t = 0; t < T; t++) { scanf("%d", &N); if (N <= 0) { printf("0\n"); continue; } for (n = 0; n < N; n++) { scanf("%d", seq + n); max_len = 1; for (k = 0; k < n; k++) if (seq[k] <= seq[n]) { len = len_lis[k] + 1; if (len > max_len) max_len = len; } len_lis[n] = max_len; } printf("%d\n", len_lis[N - 1]); } return 0; } 12년 전
3개의 댓글이 있습니다. wookayin N=4 seq[0..N-1] = {3,3,3,3} 이면 어떻게 되나요? 12년 전 link kcm1700 N=4 seq[0..N-1] = {0,1,2,0} 이면 잘 안 나올 것 같네요. len_lis[i]의 정의가 i번째 수를 포함하는 최장길이 증가수열인거죠? 문제에서 요구하는 답과 일치하는 걸 출력하게 하면 될 것 같아요. 12년 전 link jspac 윽, 그렇군요..ㅜㅜ kcm1700님, 감사합니다~ 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
jspac
http://www.algospot.com/problems/read/LIS
그냥 잘 알려진 알고리즘대로 구현했는데요..
예제로 주어진 수열들에 대해선 다 맞는 답을 내놓는데,
submit을 하면 계속 WA가 뜨네요.. 제가 구현을 잘못 한건지...
일단 소스는 아래와 같은데,
어디가 잘못된 건가요?
#include
const int MAX_LEN = 500;
int main(void)
{
int t, T, n, N, seq[MAX_LEN], k, len, max_len, len_lis[MAX_LEN];
}
12년 전