글 읽기 - 시왜맞... 잘 모르겠습니다...

eric00513 4년 전 2

제가 이 2550번을 LIS로 구현하여 맞았습니다. 저는 중간에 이중 for문이 있기 때문에 O(n²) = 10,000²이라 시간초과가 날 줄 알았는데, 왜 204ms에 통과하는지 잘 모르겠습니다. 각 스위치에 해당되는 전구의 위치를 이진탐색으로 구하고(∵ 이중 for문으로 구하면 O(n²)이라 시간초과가 날 것 같았기 때문), 단순히 LIS를 구현했습니다. 왜 시간초과가 안 나는지 모르겠습니다(시왜맞). 제발 알려주세요 ㅠㅠ 너무 궁금해요... (P.S. 제가 n=10,000인 경우가 있는지 확인해 보았는데, 데이터가 있는 것 같습니다.)

아래는 C++ 소스입니다.

#include <stdio.h>
#include <algorithm>
using namespace std;

pair<int, int> a[10001];
int sw[10001], lb[10001], index[10001], dy[10001], path[10001], all[10001];

// sw는 스위치, lb는 전구, index는 각 스위치에 연결되어 있는 전구의 번호, dy는 LIS에 필요한 배열, path는 추적 배열, all는 정답 배열

int main(void)
{
	int n, i, j;

	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%d", &sw[i]);
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &lb[i]);
		a[i] = make_pair(lb[i], i);
	}

	sort(a + 1, a + n + 1); // 이진탐색을 위해 정렬

	for (i = 1; i <= n; i++)
	{
        // 이진탐색 시작
		int left = 1, right = n + 1;
		while (left < right)
		{
			int mid = (left + right) / 2;

			if (sw[i] < a[mid].first)
				right = mid;
			else if (sw[i] > a[mid].first)
				left = mid + 1;
			else
			{
				index[i] = a[mid].second;
				break;
			}
		}
        // 이진탐색 끝
	}
	
    // LIS 시작
	for (i = 1; i <= n; i++)
		for (j = 0; j < i; j++)
			if (index[j] < index[i] && dy[i] < dy[j] + 1)
			{
				dy[i] = dy[j] + 1;
				path[i] = j;
			}
    // LIS 끝

    // LIS 배열 중 최댓값 구하기 시작
	int ans_num = 0, point = 1;
	for (i = 1; i <= n; i++)
		if (ans_num < dy[i])
		{
			ans_num = dy[i];
			point = i;
		}
    // LIS 배열 중 최댓값 구하기 끝
    
    // 추적 시작
	int tmp = path[point], cnt = 0;
	all[++cnt] = sw[point];
	while (tmp > 0)
	{
		all[++cnt] = sw[tmp];
		tmp = path[tmp];
	}
    // 추적 끝

    // 정답 출력 시작
	printf("%d\n", ans_num);
	sort(all + 1, all + cnt + 1);
	for (i = 1; i <= cnt; i++)
		printf("%d ", all[i]);
    // 정답 출력 끝
	return 0;
}

wjdclgns12 4년 전 1

1억번정도 연산이면 1초안에 충분히 돌아갑니다.

eric00513 4년 전 0

@wjdclgns12

오우 그렇군요 전 1억번 연산은 1.3초 정도 걸리는 줄 알았는데, 아닌가봐요... 감사합니다!!!

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

문제

문제

출처

ICPC

시왜맞... 잘 모르겠습니다...

eric00513 4년 전 2

wjdclgns12 4년 전 1

eric00513 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말