Script / CSS

G1sUtil.js

G1sBlogger.js

CSS

G1sNavigationList.js

Posts List


2014년 4월 13일 일요일

[Algospot] 0-1수열

0-1수열

문제 ID : ZEROONE
시간제한 : 2000ms
메모리 제한 : 65536kb
제출횟수 : 4590
정답횟수 (비율) : 945(20%)
출제자 : LIBe
출처 : 연습문제

문제자체는 간단한데 n의 값이 너무 커 시간제한이 걸리는 문제군요.
전처리 작업을 통해 시간복잡도를 O(n)으로 만들어야 시간안에 풀 수 있네요.

처음 입력받은 값을 탐색하며 0 또는 1이 몇번을 반복하고 있는지 기록한 후,
i,j 값의 큰값에서 작은 값을 뺀 값을 배열안의 값과 비교하여
작거나 같을 경우 Yes, 클 경우  No가 됩니다.

198526ZEROONEGOnecpp339B정답294ms7

시간을 많이 단축했다고 생각했는데도 더 빠른 결과를 내신분들이 많으시군요.
특히 가장 빠른 결과를 내신 err2083 님의 방법이 간단하고 좋은 것 같군요.(당연하겠지만)

>>소스보기

댓글 없음:

댓글 쓰기