글 읽기 - 코드의 문제점을 알고싶습니다.

feynp 3년 전 0

예제를 만들어 입력해봐도 제대로 나오는 듯한데, 제출 했을 때는 1%도 통과하지 못하고 틀렸습니다 라는 결과가 뜨네요.

코드의 문제점이나 반례 부탁드립니다.

로직

1. 수열의 원소가 1~N까지 값을 가지므로 numbers[원소값]에 입력되는 순서를 값으로 저장했습니다.

2. 각 부분 수열의 원소들이 연속된 값을 가지고 있어야하므로 2중 for문을 통해 {1}, {1, 2}, {1, 2, 3} ..., {1, 2, ... ,N}, {2}, {2, 3}, ... {N}과 같이 부분 수열을 이루는 원소를 선택하고,

3.각 원소들의 입력된 순서(numbers[원소값])로 부분 수열 마다 LIS의 길이를 구하였습니다.

#include <iostream>
#include <algorithm>
using namespace std;

int T, N, sum, num, tmp, cnt;
int numbers[501], lis[501];

int main() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		sum = 0;
		cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> num;
			numbers[num] = i;
		}
		for (int i = 1; i <= N; i++) {
			cnt = 0;
			for (int j = i; j <= N; j++) {
				tmp = numbers[j];
				if (cnt == 0 || lis[cnt - 1] < tmp) lis[cnt++] = tmp;
				else lis[lower_bound(lis, lis + cnt, tmp) - lis] = tmp;
				sum += cnt;
			}
		}
		cout << "Case #" << t << ": " << sum << "\n";
	}
	return 0;
}

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

문제

문제

출처

ICPC

코드의 문제점을 알고싶습니다.

feynp 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말