글 읽기 - 11003) 문제 풀이에 질문입니다. 너무 간단히 통과되는거같아요

opop20207 4년 전 3

너무 간단하게 통과되서 질문드립니다.

이게 통과되어야하는 코드가 맞나요?

제가 보기에도 알고리즘 상 허점이 많고 악의적인 테스트케이스가 주어지면 시간초과가 날거같기도 한데 진짜 아슬아슬하게 통과가 되네요...

그냥 C++이 빨라서 그런가요?

+
같은 알고리즘으로 scanf로 제출했을때는 TLE를 받았는데

cin.tie같은 전처리하고 cin, cout 사용하니 통과가 됩니다.

문제 있는거같아요

#include <queue>
#include <iostream>
using namespace std;
int N, L;
typedef pair<int, int> P;
priority_queue<P,vector<P>,greater<P>> pq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		int t1;
		int limit = i - L;
		cin >> t1;
		pq.push({ t1,i });
		while (pq.top().second <= limit) pq.pop();
		cout << pq.top().first << ' ';
	}
}

djm03178 4년 전 1

이런 류의 문제는 사실 의도된 풀이만 통과시켜줄 수 있는 시간 제한을 설정하기가 불가능에 가깝습니다. 의도된 정해가 O(N)인데, 입력량은 O(N * 자릿수)이기 때문이죠. 안 그래도 입력이라는 것 자체가 매우 느린 연산에 속하는데, 상수까지 크기 때문에 풀이가 O(NlogN)쯤 된다고 해서 입력이 느린만큼 오래 걸리지 않는 것이 보통입니다.

그래서 입력을 빠르게 받는 것만으로도 풀이의 복잡도를 개선시키는 것보다 더 큰 효과를 기대할 수 있고, ios::sync_with_stdio(false)와 cin.tie(0)은 그 정도 효과를 내기에 충분합니다.

djm03178 4년 전 0

좀 더 눈에 띄는 차이를 보여드리자면, 아래 두 코드는 모두 로직상으로는 동일한 O(N) 풀이이지만, 하나는 평범하게 printf와 scanf를 사용한 반면에 다른 하나는 fwrite와 fread로 매우 빠른 입력을 받은 모습입니다. 시간 차이가 얼마나 나는지 확인해 보세요.

https://www.acmicpc.net/source/12279924

https://www.acmicpc.net/source/12279818