본문 바로가기
알고리즘 문제/Algospot

[algospot][ITES] 외계 신호 분석

by 햄과함께 2020. 1. 31.
320x100

문제 : https://algospot.com/judge/problem/read/ITES


외부 시그널에서 신호를 새로 만들어야 한다.

생성한 시그널 = 외부시그널 % 10000 + 1
외부 시그널 = (이전 외부 시그널 * 214013 + 2531011) % 232

위 규칙으로 생성한 시그널들을 가져와서 문제를 푸는데 사용한다.

 

큐를 이용해서 풀 수 있다.

생성된 신호는 10000 나머지 연산 + 1이기 때문에 양수이다. 따라서 부분 수열은 항상 양수가 된다.

생성된 시그널을 큐에 넣으면서 부분 수열의 합을 구해나간다. 

 

만약 부분 수열의 합이 K보다 작은 경우 앞으로 생성되는 시그널들을 더하면 K가 될 수 있으므로 다음 시그널을 탐색한다.

부분 수열의 합이 K와 같은 경우는 카운팅한다.

N까지의 시그널들을 위와 같은 방법으로 탐색을 마쳤을 때 카운팅한 수가 정답이 된다.

부분 수열의 합이 K와 같거나 큰 경우는 다음 시그널을 추가한 경우 K가 나올 수 없다.

왜냐하면 앞에서 말했다시피 생성된 시그널은 양수이기 때문에 

부분 수열의 합 >= K 
부분 수열의 합 + x(앞으로 탐색할 시그널의 합) > K (x > 0)

위와 같이 항상 K보다 클 것이다.

따라서 부분 수열의 합이 K보다 작아질때까지 큐를 pop한다. (큐의 가장 앞에있는 시그널을 부분 수열의 합에서 뺀다.)

 

시간 복잡도는 O(N).


시그널 생성 방법은 같기 때문에 입력값에 상관없이 시그널은 항상 같다.

그래서 처음에는 큐를 안쓰고 투포인터 방법을 쓰기 위해 모든 시그널을 배열에 저장해서 풀었었는데 에러가 발생했다.

RTE (SIGKILL: program was forcefully killed, probably memory limit exceeded)

에러는 위와 같은데 메모리 초과때문에 발생했다.

N의 최대값은 50,000,000 이고 이를 int 형 배열에 저장한다고 하면

필요한 메모리는 50,000,000 x 4byte / 1024 = 195,312.5 kb.

따라서 이는 메모리 제한(65,536 kb)를 넘기기 때문에 에러가 발생한 것이다.

 

이를 큐를 사용하게 된다면 최대한 많이 넣는 경우 입력신호의 최소값은 1이니까 최대 K개 크기의 큐가 생성된다.

K의 최대 값은 5,000,000 이므로 메모리를 계산하면 19,531.25 kb 가 되므로 메모리 제한에 걸리지 않는다.

 

제한 사항을 잘 확인하자!

 


소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/algospot/ITES.cpp

320x100

댓글