반응형
https://www.algospot.com/judge/problem/read/ZEROONE
algospot.com :: ZEROONE
0-1수열 문제 정보 문제 0과 1로 구성된 수열이 있다. 수열의 길이가 N이라 하고, 각각의 수열의 원소마다 순서대로 번호를 매길 경우 첫 번째 숫자는 0번이 되고 두 번째 숫자는 1번, 그리고 마지
www.algospot.com
01 또는 10으로 바뀌는 순간 addIndex가 변경됨.
입력값 i, j의 차와 OUTPUT의 값을 비교하여 변경지점을 찾을 수 있음.
index Searching은 시간초과로 실패함.
#include
#define abs(a)(((a) < (0))?-(a):(a))
char INPUT[1000001];
int OUTPUT[1000001];
void SOLVE()
{
int i, j;
scanf("%d %d", &i, &j);
if (OUTPUT[(i > j) ? i : j] >= abs(i - j))
printf("Yes\n");
else
printf("No\n");
return;
}
int main()
{
int N;
scanf("%s", INPUT);
char PC = INPUT[0];
OUTPUT[0] = '0';
for (int i = 0, j = 1; INPUT[j]; j++){
if (INPUT[i] != INPUT[j])
i = j;
OUTPUT[j] = j - i;
}
scanf("%d", &N);
while (N-- > 0)
{
SOLVE();
}
return 0;
}반응형